BZOJ 1703: [Usaco2007 Mar]Ranking the Cows 奶牛排名

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1703

题意：N 只奶牛，给出 M 对大小关系，问至少添加几对关系使得能够求出所有奶牛的排名...

显然一共有 n*(n-1) 对关系，传递闭包后求出已知多少关系，用总关系数减去即为答案...

学习了一个 bitset 优化 floyd 传递闭包，结果并没有跑的很快
~~可能是写的太傻...~~

#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);
}

#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);

}

zgz233

zgz233

BZOJ 1703: [Usaco2007 Mar]Ranking the Cows 奶牛排名

l1ll5

Comments | NOTHING