原题链接

考察:floyd

思路:

        很明显的传递闭包,但是我们直接敲板子上去会TLE.神级剪枝在floyd的第三重循环,如果g[i][k] = 0那么第三重循环没必要进行.

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int N = 510;
 5 int n,m;
 6 bool g[N][N];
 7 void floyd()
 8 {
 9     for(int k=1;k<=n;k++)
10       for(int i=1;i<=n;i++)
11         for(int j=1;g[i][k]&&j<=n;j++)
12          if(g[i][k]&&g[k][j]) g[i][j] = 1;
13 }
14 int main()
15 {
16     int T;
17     scanf("%d",&T);
18     while(T--)
19     {
20         scanf("%d%d",&n,&m);
21         memset(g,0,sizeof g);
22         while(m--)
23         {
24             int a,b; scanf("%d%d",&a,&b);
25             g[a][b] = 1;//a可以胜b. 
26         }
27         floyd();
28         int ans = 0;
29         for(int i=1;i<=n;i++)
30           for(int j=i+1;j<=n;j++)
31             if(!g[i][j]&&!g[j][i]) ans++;
32         printf("%d\n",ans);
33     }
34     return 0;
35 }