搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > POJ-3275:奶牛排序Ranking the Cows(Floyd、bitset)

POJ-3275:奶牛排序Ranking the Cows(Floyd、bitset)

2019-02-15
举报

Description


Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.


农夫John的N头奶牛产奶的速率都不同,John想对这些奶牛的产奶速率进行排序。


FJ has already compared the milk output rate for M (1 ≤ M ≤ 10,000) pairs of cows. He wants to make a list of additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible.


John已经比较了M对奶牛的产奶率。他想列一个清单,如果他比较了C对奶牛,他就能推测出所有奶牛N的顺序。你需要帮助John算出最小对数C。


Input


Line 1: Two space-separated integers: N and M 
Lines 2..M+1: Two space-separated integers, respectively: X and Y. Both X and Y are in the range 1...N and describe a comparison where cow X was ranked higher than cow Y.


Output


Line 1: A single integer that is the minimum value of C.


Sample Input


5 5 2 1 1 5 2 3 1 4 3 4


Sample Output


3


Hint


From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: "Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?"

 

概译:

        农夫有N头牛,他要给牛排名,他已经知道M对牛的相对排名(比如X>Y),求出他还需要知道多少对,就能准确地将所有牛排名。


输入:

        输入N,M。接下来的M行每行输入X,Y,代表X>Y。


思路:

        当任意两头牛都明确知道相对rank时,即可以准确排名,此时共须知n*(n-1)/2对。已给M对,再求出这M对所隐藏的排名共ans对(例:2>1,1>5是M对里给出的,则2>5是隐藏的一对),则n*(n-1)/2 - M - ans就是最后的输出。

        

        可视为有向图,2>1则画出一条2指向1的边,用Floyd就可以完成对隐藏路径的连通。O(N³)复杂度较高,此题M(边数)较少,可以用枚举边的方式,输入时记录每个节点的入边和出边,Floyd时枚举每个转折点的入边和出边。


#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;

int n,m,ans;
bool mp[1005][1005];
vector<int>ru[1005],chu[1005];

int main()
{
    scanf("%d%d",&n,&m);

    for (int i = 0; i < m; i++)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        ru[b].push_back(a);
        chu[a].push_back(b);
        mp[a][b] = true;
    }

    for (int k = 1; k <= n; k++)
        for (int a = 0; a < ru[k].size(); a++)
            for (int b = 0; b < chu[k].size(); b++)
            {//C++11的“int i:ru[k]”POJ貌似编译不过去
                int i = ru[k][a];
                int j = chu[k][b];
                if(!mp[i][j])
                {
                    ru[j].push_back(i);
                    chu[i].push_back(j);
                    mp[i][j] = true;
                    ans++;
                }
            }

    printf("%d\n",(n-1)*n/2-m-ans);

    return 0;
}


也可以使用STL容器bitset,它使得mp数组以二进制01串形式进行位运算,通常可以将复杂度除以64。


使用详见代码:


#include<cstdio>
#include<bitset>
#include<iostream>
using namespace std;

const int maxn=1000+5;
int n,m,ans;
bitset<maxn>bit[maxn];//类似于上面那个方法的mp二维数组

int main()
{
    scanf("%d%d",&n,&m);

    for (int i = 0; i < m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        bit[a].set(b);//将bit[a][b]设为1
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (bit[j][i])//这其实就是个暴力的Floyd
                bit[j] |= bit[i];//或运算使得i中为1的点(即有向图中i指向的点),j也指向它

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (bit[i][j])
                ans++;
    //这里的ans是枚举之后得到的所有边,已经Floyd处理过了,所以包括隐藏的

    cout << n*(n-1)/2-ans << endl;

    return 0;
}


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《POJ-3275:奶牛排序Ranking the Cows(Floyd、bitset)》的版权归原作者「ACM算法日常」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注ACM算法日常微信公众号

ACM算法日常微信公众号:acm-clan

ACM算法日常

手机扫描上方二维码即可关注ACM算法日常微信公众号

ACM算法日常最新文章

精品公众号随机推荐

举报