Description
农夫约翰有N(1≤N≤1000)头奶牛，每一头奶牛都有一个确定的独一无二的正整数产奶率．约翰想要让这些奶牛按产奶率从高到低排序． 约翰已经比较了M(1≤M≤10000)对奶牛的产奶率，但他发现，他还需要再做一张关于另外C对奶牛的产奶率比较，才能推断出所有奶牛的产奶率排序．请帮他确定C的最小值．
Input
第1行包含两个用空格分开的整数N和M.接下来M行，每行有两个用空格分开的整数X和Y(1≤X，y≤1000)，表示奶牛X的产奶率高于奶牛Y.
Output
C的最小值．
Sample Input
5 5
2 1
1 5
2 3
1 4
3 4
2 1
1 5
2 3
1 4
3 4
INPUT DETAILS:
FJ is comparing 5 cows and has already determined that cow 2 > cow
1, cow 1 > cow 5, cow 2 > cow 3, cow 1 > cow 4, and cow 3 > cow 4
(where the '>' notation means "produces milk more quickly").
Sample Output
3
答案为排名无序的点对个数……
然后就总点对-排名有序点对数咯。
#include<bitset>
#include<cstdio>
#include<algorithm>
using namespace std;
int read_p,read_ca,read_f;
inline int read(){
read_p=;read_ca=getchar();read_f=;
while(read_ca<''||read_ca>'') read_f=read_ca=='-'?-:read_f,read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p*read_f;
} int n,m,mmh,x,y;
bool bo[];
bitset <> b[];
void dfs(int x){
if (bo[x]) return;bo[x]=;
for (int i=;i<n;i++)
if (b[x][i]) dfs(i),b[x]|=b[i];
}
int main(){
register int i;
n=read();m=read();mmh=(n*(n-))>>;
for (i=;i<=m;i++) x=read()-,y=read()-,b[x][y]=;
for (i=;i<n;i++) dfs(i),mmh-=b[i].count();
printf("%d\n",mmh);
}
948 kb 104 ms C++/Edit 796 B