Week7 作业 A

题目描述：

有N个人，M个胜负关系，胜负关系用A B表示，表示A能胜过B，胜负关系具有传递性。问这N个人的两两比赛中，有多少个胜负关系不能通过给定的M个胜负关系事先确定。

思路：

不能确定的关系=N*（N-1）/2 - 能确定的关系，求能确定的关系很显然就是求关系的传递闭包中，有多少个序偶。

直接用沃舍尔算法求解，关系直接用数组dis[i][j]表示，存在关系（i，j），则dis[i][j]==1；

算法中，值得注意的是，只用已经有的关系去更新关系，即当关系（i，k）不存在时，（k，j）就不可能被更新。

代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 const int MAXN=505;
 6 int dis[MAXN][MAXN];
 7 int T,N,M;
 8 int main()
 9 {
10     cin>>T;
11     while(T--)
12     {
13         memset(dis,0,sizeof(dis));
14         cin>>N>>M;
15         for(int i=1;i<=M;i++)
16         {
17             int A,B;
18             scanf("%d %d",&A,&B);
19             dis[A][B]=1;   //A->B 有一条有向边 
20         }
21         //求关系的传递闭包 
22         for(int k=1;k<=N;k++)
23             for(int i=1;i<=N;i++)
24             {
25                 if(dis[i][k]==0) continue;
26                 for(int j=1;j<=N;j++)
27                 {
28                     if(dis[i][k]==1&&dis[k][j]==1) dis[i][j]=1;
29                 }
30             }
31         int ans=0;
32         for(int i=1;i<=N;i++)
33             for(int j=1;j<=N;j++)
34                 if(dis[i][j]==1) ans++; 
35         cout<<N*(N-1)/2-ans<<endl;
36     }
37     return 0;
38 }