放水三人组的数量，求解

有n人两两比赛，比赛结果只有胜负，没有平。
如果ABC三人出现A胜B,B胜C,C胜A的情况，认为这三人放水。
n人编号为1至n
输入一个n*n的矩阵M，Mij为1时指i胜j,Mij为-1时指i输j, 所有Mii为0
输出放水三人组的数量，要求算法复杂度为O(n^2)

输入是带n的
例如
输入
4
0 1 -1 -1
-1 0 -1 1
1 1 0 -1
1 -1 1 0
输出
2
输入
4
0 -1 -1 -1
1 0 -1 -1
1 1 0 -1
1 1 1 0
输出
0

不感兴趣

开通SVIP免广告

答案是这样
最大可能组数为n*(n-1)*(n-2)/6
对每个人i, ta的获胜场数为Wi, 则从最大可能组数里减去Wi(Wi-1)/2
n*n的矩阵循环一遍，复杂度是O(n^2)
这里不清楚
对每个人i, ta的获胜场数为Wi, 则从最大可能组数里减去Wi(Wi-1)/2
求解释

有大佬给我解答了：三人组如果有人赢了两场，则没有放水
对每个人，选择ta获胜的两场比赛，对应一个不放水三人组
所以放水三人组=nC3-Σ(WiC2)

下载贴吧APP
看高清直播、视频！

分享到: