HDU1704 Rank——传递闭包(Floyd)

tech2022-09-26  75

点这里

题意: n个人和m场一对一的比赛,问比赛完之后,还有多少排名关系不能确定。 题解: 谈谈传递闭包以及自己杂想、传递闭包     知道传递闭包的话就不用多解释了。


过程中犯的错:

TLE: Floyd虽然好用,但是输在时间复杂度上,因此在第二个for循环的下面加了一个if语句,可以减少一些时间复杂度。
#include<bits/stdc++.h> using namespace std; const int N = 510; int T, n, m, a, b; int G[N][N]; void Floyd(){ for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) if(G[i][k]) for(int j = 1; j <= n; j++) if(G[k][j]) G[i][j] = 1; } int main(){ scanf("%d", &T); while(T--){ memset(G, 0, sizeof G); scanf("%d%d", &n, &m); while(m--){ scanf("%d%d", &a, &b); G[a][b] = 1; } Floyd(); int sum = 0; for(int i = 1; i <= n; i++) for(int j = 1; j < i; j++) if(!G[i][j] && !G[j][i]) sum++; printf("%d\n", sum); } return 0; }
最新回复(0)