预测胜负

问题描述

N 个人玩一个游戏，每两个人都要进行一场比赛。
已知 M 个胜负关系，每个关系为 A B，表示 A 比 B 强， 胜负关系具有传递性。
试问有多少场比赛的胜负无法预先得知？

Input

第一行给出数据组数。
每组数据第一行给出 N 和 M（1 ≤ N, M ≤ 500）。
接下来 M 行，每行给出 A B，表示 A 可以胜过 B。

Output

对于每一组数据，判断有多少场比赛的胜负不能预先得知。
注意 (a, b) 与 (b, a) 等价，即每一个二元组只被计算一次。

Sample

Input: 
3
3 3
1 2
1 3
2 3
3 2
1 2
2 3
4 2
1 2
3 4
Output: 
0
0
4

Limitation

Time limit		1000 ms
Memory limit	32768 kB

解题思路

Floyd算法：用于寻找加权图中顶点间最短路径的算法。在 n × n 的矩阵 M 中，M[i][j]表示顶点i到顶点j的距离，然后对矩阵进行 n 次更新，第 k 次更新时，如果M[i][j] > M[i][k] + M[k][j]，则更新为M[i][k] + M[k][j]。

本题可用二维数组来表示每个人之间的胜负关系，初始时值为0，表示关系不明。
由于胜负关系具有传递性，比如a > b, b > c, 则 a > c，因此可用Floyd算法更新任意两人之间的胜负关系：
若arr[a][b] = 1，则a胜b；
若arr[a][b] = 0，则a与b胜负关系不明；
若arr[a][b] = 1且arr[b][c] = 1，则arr[a][c] = 1；
若arr[a][b] = 0且arr[b][a] = 0，则a与b的胜负关系无法预先判断。

所以最后确定多少场无法预知结果的比赛，只需计算arr[a][b] = 0 && arr[b][a] == 0 && a != b的个数，结果再除以2即可。

源代码

#include <iostream>
using namespace std;

const int maxN = 505;

int main() {
	int t;
	cin >> t;
	for (int i0 = 0; i0 < t; i0++) {
		int n, m;
		cin >> n >> m;
		
		int arr[maxN][maxN] = { 0 };
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			arr[a][b] = 1;
		}
		// Floyd 算法
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (arr[j][i] == 1)//已知道了两人关系 再进行更新第三人
					for (int k = 1; k <= n; k++)
						if (arr[i][k] == 1)
							arr[j][k] = 1;
		int count = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != j && arr[i][j] == 0 && arr[j][i] == 0)
					count++;
		cout << count / 2 << endl;// i 求了一遍，j 又求了一遍，所以要减半
	}
	return 0;
}