链接：https://ac.nowcoder.com/acm/contest/26077/1024
来源：牛客网
题目描述
Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.FJ has already compared the milk output rate for M (1 ≤ M ≤ 10,000) pairs of cows. He wants to make a list of C additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible.
输入描述:
Line 1: Two space-separated integers: N and M
Lines 2..M+1: Two space-separated integers, respectively: X and Y. Both X and Y are in the range 1...N and describe a comparison where cow X was ranked higher than cow Y.
输出描述:
Line 1: A single integer that is the minimum value of C.示例1
输入
复制5 5 2 1 1 5 2 3 1 4 3 4
输出
复制3
说明
From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: "Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?"
分析
题意，大概是已经确定好了一部分的两两关系，让我推出总共已经确定好了多少两两关系，然后看看还剩下多少两两关系没有推出来
其中已经确定好的那些两两关系是一大一小的关系，剩下的关系不知道是相等还是不相等，所以得用总的关系数减去已经推出来的关系数。
可以用floyd传递闭包来确定总共确定了多少关系，如果a < b ,b<c => a < c
for(int k = 1;k<=n;k++)
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
p[i][j] |= p[i][k] & p[k][j];
floyd 的本质：设p[i][k] 表示对于i，已经确定好了所有标号 小于等于 k - 1 的点为中转点得到的情况，再求以前k个点为中转点得到的情况
对于这题来说，信息就是两个点是否有关系，可以用1和0表示
普通的floyd传递闭包：（未优化第一维）
for(int k = 1;k<=n;k++)
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
f[k][i][j] |= f[k-1][i][k] & f[k-1][k][j];
bitset优化，存储了 i 这个点的所有点的关系
假如 i 和 第k 个点有关系，且已经经过 前 k - 1个点，可以写成
for(int k = 1;k<=n;k++)
for(int i = 1;i<=n;i++)
if(f[k - 1][i][k]) f[k][i][k] |= f[k-1][k];
第一维省去就是
for(int k = 1;k<=n;k++)
for(int i = 1;i<=n;i++)
if(f[i][k]) f[i] |= f[k];
//-------------------------代码----------------------------
//#define int ll
const int N = 1010;
int n,m;
bitset<N> p[N];
void solve()
{
cin>>n>>m;
fo(i,1,n) {
// p[i][i] = 1;
}
while(m--) {
int x,y;cin>>x>>y;
p[x][y] = 1;
}
fo(k,1,n) {
fo(i,1,n) {
if(p[i][k]) {
p[i] |= p[k];
}
}
}
int ans = 0;
fo(i,1,n) {
ans += p[i].count();
}
cout<<n * (n-1) / 2 - ans<<endl;
}
void main_init() {}
signed main(){
AC();clapping();TLE;
cout<<fixed<<setprecision(12);
main_init();
// while(cin>>n,n)
// while(cin>>n>>m,n,m)
// int t;cin>>t;while(t -- )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//------------------------------------------------------------
标签：关系,1024,Mar,cow,Ranking,int,floyd,cows,he From： https://www.cnblogs.com/er007/p/16602974.html