NC25064. [USACO 2007 Mar G]Ranking the Cows

描述

输入描述

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?"

原站题解

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
bitset<N>b[N];
int main(){
	int n,m,i,j;
	for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),b[i][j]=1;
	for(i=1;i<=n;++i)for(j=1;j<=n;++j)if(b[j][i])b[j]|=b[i];
	for(j=n*(n-1)/2,i=1;i<=n;++i)j-=b[i].count();
	printf("%d",j);}