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

n<=1000头牛各有一个未知值Ai，已知m<=10000条形如Ax>Ay的不等关系，求将整个序列排序的最少比较次数。

Aa>Ab，Ab>Ac -------> Aa>Ac，传递性，因此按m条不等关系连边建图，求出传递闭包，就是已知的关系。

求出传递闭包中的i≠j的0的个数即可。错误！连的图是有向图，而已知大于关系后其实另一边已知一个小于关系，所以用n*n，减去1的个数*2，再减(i,j),i=j的n个，再除以2得到答案。

n³不可接受，因此用bitset优化floyd。代码如下：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<bitset>

 //#include<iostream>

 using namespace std;

 int n,m;

 #define maxn 1011

 #define maxm 10011

 struct Edge{int to,next;};

 struct Graph

 {

     bitset<maxn> mp[maxn];

     Graph() {memset(mp,,sizeof(mp));}

     void insert(int x,int y) {mp[x][y]=;}

     void floyd()

     {

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

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

                 if (mp[i][j]) mp[i]|=mp[j];

     }

     int getans()

     {

         int one=;

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

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

                 one+=mp[i][j];

         return (n*(n-)-one*)/;

     }

 }G;

 int x,y;

 int main()

 {

     scanf("%d%d",&n,&m);

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

     {

         scanf("%d%d",&x,&y);

         G.insert(x,y);

     }

     G.floyd();

     printf("%d\n",G.getans());

     return ;

 }

其实这个题是个错题，但错题错做。比如输入5 0，答案是10，但可以比较8次就出来。就是在一个已知有序数列中二分插入一个数，只是人工处理的情况下不需要进行区间移动之类的。

巴特西

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

最新文章

热门文章