floyd

佚名 4年前 (2020-06-16) 算法 676人围观抢沙发百度已收录

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 const int N = 110;
 8 int f[N][N];
 9 
10 //核心想法：//i到达j经过前k个城市
11 //下面表示的是可以确定几个人的排名
12 //样例：
13 //5 5  n m 单向
14 //4 3 u v
15 //4 2
16 //3 2
17 //1 2
18 //2 5
19 //可以确定2和5的排名，rank[2] = 4, rank[5] = 5
20 
21 void solve(){
22 
23     int n, m;
24     scanf("%d%d", &n, &m);
25 
26     int u, v;
27     for(int i = 0; i < m; ++i){
28         scanf("%d%d", &u, &v);
29         f[u][v] = 1;
30     }
31 
32     for(int i = 1; i <= n; ++i) f[i][i] = 1;
33 
34     //i到达j经过前k个城市
35     for(int k = 1; k <= n; ++k){
36         for(int i = 1; i <= n; ++i){
37             for(int j = 1; j <= n; ++j){
38                 f[i][j] = f[i][j] | (f[i][k] & f[k][j]);
39             }
40         }
41     }
42 
43     int cows = 0;
44     for(int i = 1; i <= n; ++i){
45         int cnt = 0;
46         for(int j = 1; j <= n; ++j){
47             cnt += (f[i][j] | f[j][i]);
48         }
49         //能确定前面有几个rank大于它，后面有几个rank小于它
50         if(cnt == n) ++cows;
51     }
52 
53     printf("%d\n", cows);
54 }
55 
56 int main(){
57 
58     solve();
59 
60     return 0;
61 }