【BZOJ1703】奶牛排名-白红宇

【BZOJ1703】奶牛排名

阅读量：5830 次

发布时间：2019-06-18

本文共 2162 字，大约阅读时间需要 7 分钟。

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

Time Limit: 5 Sec Memory Limit: 64 MB

Submit: 415 Solved: 288

[ ][ ][ ]

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

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
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #define debug(x) cerr<<#x<<"="<
                    
                     <
                     
                       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\n",ans); return 0;}

View Code

转载于:https://www.cnblogs.com/redwind/p/6589417.html

你可能感兴趣的文章