hdu 4324 Triangle LOVE(拓扑排序,基础)

 

题目

 

/***************************参考自****************************/

http://www.cnblogs.com/newpanderking/archive/2012/10/16/2726757.html

上有详细注解,我是看了之后写的,我的代码有一咪咪的改动

//这是一道典型的拓扑排序的题,刚开始时没有理解,
//上网查了好多关于拓扑排序的知识才明白,
//就是针对一个顶点活动网(Activity On Vertex network),简称AOV网,
//从中去除入度为0的顶点,同时更新从改点出发引起的入度,
//让这些点的入度减1,直到最后如果AOV网为空时,
//说明那么去除的这些点就组成了一个拓扑排序,
//如果AOV网不为空,这种情况若在程序中出现,
//则称为死锁或死循环(即形成环),是应该必须避免的,
//说明这些活动是永远执行不到的(在此题中是Yes)。
//(活动的前驱又是在活动之后执行)

/***********************************************************/

 

hdu 4324 Triangle LOVE(拓扑排序,基础)
#define  _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char love[2010][2010];
int in_degree[2010];
int flag;
int tuopu(int n)
{
    int i,j,jj;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(in_degree[j]==0)
            {
                in_degree[j]=-1;
                break;
            }
        }
        if(j==n)
        {
            return 1;
        }
        else
        {
            for(jj=0;jj<n;jj++)
            {
                if(love[j][jj]==1)
                    in_degree[jj]--;
            }
        }
    }
    return 0;
}
int main()
{
    int t,i,j,n,id;
    scanf("%d",&t);
    for(id=1;id<=t;id++)
    {
        memset(in_degree,0,sizeof(in_degree));
        memset(love,0,sizeof(love));
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%s",love[i]);
            for(j=0;j<n;j++)
                if(love[i][j]==1)
                    in_degree[j]++;
    
        }
        flag=tuopu(n);
        printf("Case #%d: ",id);
        if(flag==1)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
View Code

 

 

//其实我原本是为了搜强连通分量的,然后搜到了这道题;也就是说,这题也可以用 强连通 来做

hdu 4324 Triangle LOVE(拓扑排序,基础)

上一篇:系统架构所需要的技术1


下一篇:java 读写文件例子