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

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 C 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;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-07-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Golang泛型编程初体验

序言 众所周知,Golang中不支持类似C++/Java中的标记式泛型,所以对于常用算法,比如冒泡排序算法,有些同学容易写出逻辑上重复的代码,即整型是第一套代码...

1.6K8
来自专栏Coding迪斯尼

面试算法:二分查找法寻找数组截断点

1032
来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(下)

一般来说,默认参数比方法族(method families)更可取,因为它减轻了 API 使用者的认知负担。

732
来自专栏ml

排序一栏(总结帖)

      学了很多的排序,基数排序,堆排序,希尔排序,选择排序,归并排序,快速排序,冒泡排序.....等等,尽管网上好文,如堆山之牛毛,但是还是没有自己写,来...

2103
来自专栏菜鸟前端工程师

JavaScript学习笔记018-面向对象编程思维0构造函数0Class

1052
来自专栏web编程技术分享

js常用方法和一些封装(3) -- dom相关

42610
来自专栏AI派

Pandas基本功能详解 | 轻松玩转Pandas(2)

在 Pandas数据结构详解 | 轻松玩转Pandas(1) 介绍了 Pandas 中常用的两种数据结构 Series 以及 DataFrame,这里来看下这...

1342
来自专栏数据结构与算法

P1774 最接近神的人_NOI导刊2010提高(02)

题目描述 破解了符文之语,小FF开启了通往地下的道路。当他走到最底层时,发现正前方有一扇巨石门,门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“...

2726
来自专栏编程微刊

JavaScript经典面试题之简单算法

在 Virtual DOM 的基础上给 VNode 类添加 render 方法,render 方法把一个虚拟的 DOM 节点渲染成真正的 DOM 节点,例如:

1791
来自专栏移动端开发

快速排序OC、Swift版源码

前言: 你要问我学学算法在工作当中有什么用,说实话,当达不到那个地步的时候,可能我们不能直接的感觉到它的用处!你就抱着这样一个心态,当一些APP中涉及到算法...

2208

扫码关注云+社区

领取腾讯云代金券