题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1703
题意：N 只奶牛，给出 M 对大小关系，问至少添加几对关系使得能够求出所有奶牛的排名...
显然一共有 n*(n-1) 对关系，传递闭包后求出已知多少关系，用总关系数减去即为答案...
学习了一个 bitset 优化 floyd 传递闭包，结果并没有跑的很快
可能是写的太傻...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <cmath> #include <queue> #include <bitset> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 1010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bitset<N> a[N]; int n,m,x,y,ans; int main() { n=read(),m=read(); for(int i=1;i<=n;i++)a[i][i]=1; for(int i=1;i<=m;i++) { x=read(),y=read(); a[x][y]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(a[i][k])a[i]|=a[k]; ans=n*(n-1)/2; for(int i=1;i<=n;i++) ans-=a[i].count(); printf("%d",ans+n); } |
Comments | NOTHING