【POJ 3275】Ranking the Cows 题解（传递闭包）

农夫约翰的N头奶牛（1≤N≤1000）产奶率各不相同，FJ希望根据这些比率从最快的奶牛到最慢的奶牛订购奶牛。
FJ已经比较了M（1≤M≤10000）对奶牛的产奶率。他想列出另外C对奶牛的列表，这样，如果他现在比较这些C对奶牛，他肯定能够推断出所有N头牛的正确顺序。请帮助他确服务器托管网定C的最小值，这样的列表是可能的。

输入
第1行：两个空格分隔的整数：N和M
第2..M+1行：分别是两个空格分隔的整数：X和Y。X和Y都在1…N的范围内，并描述了奶牛X的排名高于奶牛Y的比较。
输出
第1行：服务器托管网一个整数，是C的最小值。

Sample
Input
5 5
2 1
1 5
2 3
1 4
3 4
Output
3

思路

根据排列组合易知，总关系数目为n * (n – 1) / 2。用一个位集合记录大小关系。大小关系具有传递性，若a > b > c，则必有a > c。通过这一结论，利用按位或运算，推断隐含的大小关系。最后统计已知的关系数目，用总关系数目减去已知关系数目得到待求关系数目。

AC代码

#include 
#include 
using namespace std;
#define AUTHOR "HEX9CF"

bitset bs[1005];

int main()
{
    int n, m;
    int cnt = 0;
    cin >> n >> m;
    int c = n * (n - 1) / 2;
    for (int i = 0; i > a >> b;
        bs[a][b] = 1;
    }

    for (int j = 1; j  b, b > c
            if (bs[i][j])
            {
                // a > c
                bs[i] |= bs[j];
            }
        }
    }
    for (int i = 1; i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 基于Springboot+Vue的校园招聘系统（进阶版）
一. 🦁 前言
二. 🦁 开源代码与组件使用情况说明
三. 🦁 核心功能
四. 🦁 演示效果
五. 🦁 总结

本项目是一年前写的一个项目的升级版，因为某些原因将它作了一个升级改进， 好多兄弟来问有没有演示，现在先来写个说明！！！ 目录 一. 🦁 前言 二. 🦁 开源代码与组件使用情况说明 三. 🦁 核心功能 1. 算法设计 2. Md5加密算法 3. 文件上传设计 4…