题意:N 个人,M 场比赛,每场比赛第一个数是胜者,胜负关系具有传递性。问这些人不能确定胜负关系有几对。POJ3360 与此题题意相同,只不过改成了求能确定排名的人数(一个人与其他所有人的胜负关系都是确定的情况下就能确定排名)。
给出 HDU1704 的 AC 代码,POJ3360 在此代码稍微修改下即可。
#include<iostream> #include<cmath> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n, m; int pic[600][600]; int main(){ //freopen("a.txt", "r", stdin); int t; cin >> t; while(t--){ memset(pic, 0, sizeof(pic)); scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) pic[i][i] = 1; while(m--){ int a, b; scanf("%d %d", &a, &b); pic[a][b] = 1; } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ if(pic[i][k]){ for(int j = 1; j <= n; j++){ if(pic[k][j]) pic[i][j] = 1; } } } } int ans = 0; for(int i = 1; i <= n; i++) for(int j = i+1; j<= n; j++){ if(!pic[i][j] && !pic[j][i]) ans++; } cout << ans <<endl; } return 0; }