【BZOJ1703】奶牛排名

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

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 415 Solved: 288
[Submit][Status][Discuss]

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

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

HINT

从输入样例中可以发现，约翰已经知道的排名有奶牛2>奶牛1>奶牛5和奶牛2>奶牛3>奶牛4，奶牛2排名第一．但是他还需要知道奶牛1的名次是否高于奶牛3来确定排名第2的奶牛，假设奶牛1的名次高于奶牛3．接着，他需要知道奶牛4和奶牛5的名次，假设奶牛5的名次高于奶牛4．在此之后，他还需要知道奶牛5的名次是否高于奶牛3．所以，他至少仍需要知道3个关于奶牛的排名．

Source

Gold

SOL：

闲来无聊找到的bitset优化传递闭包

挺裸的

注意一点传递闭包的顺序不要搞错了

为啥？

考虑这张图：

1->2

2->3

2->4

2->5

3->6

假如我们第一层循环是起点，第二层循环是重点那么

1->2->3可以确定

1->2->3->6无法确定

对于正解：

2<-1可以确定

3<-2可以确定

6<-3可以确定

那么整体可以确定

（总而言之就是k放最外边别SB就好）

/*To The End Of The Galaxy*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<bitset>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#define debug(x) cerr<<#x<<"="<<x<<endl
#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
#define P(x,y) (((x-1)*c)+y)
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{
    int now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
inline long long llinit()
{
    long long now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
bitset<1010> mat[1010];
int main()
{
    int n,m,a,b;
    n=init();m=init();
    for(int i=1;i<=m;i++)
    {
        a=init();b=init();
        mat[a][b]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mat[j][i])mat[j]|=mat[i];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(i!=j&&!mat[i][j]&&!mat[j][i])
            {
                ans++;
            }
        }
    }
    printf("%d
",ans);
    return 0;
}

View Code