Bzoj 1703: [Usaco2007 Mar]Ranking the Cows 奶牛排名传递闭包,bitset

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

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 323 Solved: 238
[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

题解：

首先，看到每行为x大于y，可以想到我们可以把每行看为有向边x->y。然后在纸上画一画，我们发现，这道题其实要求的是有多少个点对(i,j) (1<=i,j<=n)，满足i通过有向图中的边到不了j且j通过有向图的边也到不了i。之后就是直接用Warshall求传递闭包(其实跟floyd差不多,2333)。但是我们不能用三重循环求解，会超时。于是就想到用bitset优化即可。

代码很短。。。

 #include<bits/stdc++.h>

 using namespace std;

 bitset<> a[];

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 int main()

 {

     int n,m,x,y,k,i,j,ans;

     n=read();m=read();

     //for(i=1;i<=n;i++)a[i].reset();

     for(i=;i<=m;i++)

     {

         x=read();y=read();

         a[x][y]=;

     }

     //for(i=1;i<=n;i++)a[i][i]=1;

     for(i=;i<=n;i++)

     {

         for(j=;j<=n;j++)

         {

             if(a[j][i])a[j]|=a[i];//j既然能到i,那么也可以到i能到的所有点.

         }

     }

     ans=;

     for(i=;i<=n;i++)

     {

         for(j=i+;j<=n;j++)

         {

             if(a[i][j]==&&a[j][i]==)ans++;

         }

     }

     printf("%d",ans);

     fclose(stdin);

     fclose(stdout);

     return ;

 }

Bzoj 1703: [Usaco2007 Mar]Ranking the Cows 奶牛排名 传递闭包,bitset