USACO2007MAR GOLD 奶牛排名

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Sep 05 15:25:11 CST 2018

In Category: NoCategory

Description：

给出 $m$ 个形如 $A$ 排名比 $B$ 高的关系，问最少知道另外几个关系，就能知道所有排名。

$1\le n\le 1000$

Solution：

由于必须保证能知道所有排名，所以以前大小关系不确定的都必须确定，才能保证无论哪种情况都有解，确定大小关系用 $bitset$ 优化 $floyed$ 传递闭包。

复杂度 $O(n^3/32)$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<bitset>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

bitset<MAXN> f[MAXN];

int main()

{

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

    int a,b;

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

    {

        scanf("%d%d",&a,&b);

        f[a][b] = true;

    }

    for(int k = 1;k <= n;++k)

    {

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

        {

            if(f[i][k])

            {

                f[i] |= f[k];

            }

            /*

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

            {

                f[i][j] |= f[i][k] & f[k][j];

            }

            */

        }

    }

    int ans = 0;

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

    {

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

        {

            if(!f[i][j] && !f[j][i])++ans;

        }

    }

    cout << ans << endl;

    return 0;

}

In tag: 图论-连通性-floyed传递闭包技巧-bitset

wjh15101051