POJ 3660 Cow Contest (FLOYD 扩展)

 1 /floyd求传递闭包，裸题，当牛被打败x次，胜利y次，且x+y==n-1时，说明该牛位置确定。注意下面的程序中
 2 //map[i][i]恒为false，也就是自己不能打败自己。难度1
 3 
 4 #include<stdio.h>
 5 #include<string.h>
 6 int n,m;
 7 int map[500][500];
 8 void floyd()
 9 {
10     int i,j,k;
11     for(k=1;k<=n;k++)
12     {
13         for(i=1;i<=n;i++)
14           for(j=1;j<=n;j++)
15          {
16             if(map[i][k]&&map[k][j])map[i][j]=1;
17          }
18     }
19 }
20 int main()
21 {
22     int i,a,b,j;
23     while(scanf("%d%d",&n,&m)!=EOF)
24     {
25         memset(map,0,sizeof(map));
26         for(i=1;i<=m;i++)
27         {
28             scanf("%d%d",&a,&b);
29             map[a][b]=1;
30         }
31         floyd();
32         int ans=0;
33         for(i=1;i<=n;i++)
34         {
35             int sum=0;
36 
37            for(j=1;j<=n;j++)
38            {
39                if(map[i][j]||map[j][i])sum++;
40            }
41            if(sum==n-1)ans++;
42         }
43         printf("%d\n",ans);
44     }
45 
46 }