poj 3660 Cow Contest

Cow Contest

题目链接：http://poj.org/PRoblem?id=3660

题目大意：求出能够确定排名的牛的个数。

有点类似于闭包传递，转化成图的连通性。最后统计各点的出入度等于n-1的便是符合要求的。

代码如下：

#include<cstdio>#include<iostream>#include<cstring>#define INF 100000000using namespace std;int map[105][105];int dis[105],vi[105];int ans[105];void Dj(int x,int n){	for(int i=1;i<=n;i++)	{		dis[i]=map[x][i];		vi[i]=0;	}	vi[x]=1;	for(int i=2;i<=n;i++)	{		int p;		for(int j=1;j<=n;j++)		{			if(!vi[j] && dis[j]<INF)			{				p=j;				break;			}		}		vi[p]=1;		for(int j=1;j<=n;j++)		{			if(!vi[j] && dis[j]>=map[p][j])				dis[j]=map[p][j];		}	}}int main(){	int n,m;	int x,y;	int sum;	while(~scanf("%d%d",&n,&m))	{		sum=0;		for(int i=0;i<=n;i++)			ans[i]=0;		for(int i=0;i<=n;i++)			for(int j=0;j<=n;j++)				map[i][j]=INF;		for(int i=0;i<m;i++)		{			cin>>x>>y;			map[x][y]=1;		}		for(int i=1;i<=n;i++)		{			Dj(i,n);			for(int j=1;j<=n;j++)			{				if(dis[j]<INF)				{					ans[j]++;					ans[i]++;				}			}		}		for(int i=1;i<=n;i++)		{			if(ans[i]==n-1)			{				sum++;			}		}		printf("%d/n",sum);	}		return 0;}