poj 3660 Cow Contest
Cow Contest
题目链接:http://poj.org/PRoblem?id=3660
题目大意:求出能够确定排名的牛的个数。
有点类似于闭包传递,转化成图的连通性。最后统计各点的出入度等于n-1的便是符合要求的。
代码如下:
#include<cstdio> #include<iostream> #include<cstring> #define INF 100000000 using 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; }