P2881 [USACO07MAR]Ranking the Cows G

简介: P2881 [USACO07MAR]Ranking the Cows G

题目描述


20210507145144759.png


输出格式


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


输入输出样例


输入样例


5 5

2 1

1 5

2 3

1 4

3 4


输出样例


3


题目分析


这个题主要考察图的应用.

我们可以把牛头数作为图的结点,把产奶能力作为图中的关系,可以做下图所示的转换:

20210225145640278.jpg

然后根据已知条件:<1,5> <1,4>,<2,1> 可推得<2,4>,<2,5>.总共7种关系.而有向图最多有s = n*(n-1) /2 种关系.所以还需要的就是: s - 已知的七种;

如何得到己知关系呢?


可以利用bitset 位运算 ,每个结点用一个bitset表示。具体如何使用可以点击这里

bitsetp[maxn];-


建立一个 位数的二进制数组。

初始化时,p[i][i]=1, 即p[i]的第i位为1. 也就是自己能推出自己.

输入1—5,令p[1][5]=1,则p[1] = …00000 //从右往左数到第5个然后把值变为1,表示<1,5>

输入1—4,令p[1][4]=1,则p[1] = …110010.0//从右往左数到第4个然后把值变为1,表示<1,4>

输入2—1,令p[2][1]=1, 则p[2] = …0011000

输入2—3,令p[2][3] =1,则p[2] = …01110

输入3—4,令p[3][4]=1,则p[3] = …11000

判断每个数组的每一位:

if(p[i][k])

     p[i] = p[i] | p[j]

例如p[2][1]=1,则p[2]= p[2] | p[1]= 001110|110010111110;

2和1有关系,而1和4、5有关系,通过或运算,可以得出2和4、5也有关系。


参考代码

#include<iostream>
#include<bitset>
using namespace std;
const int maxn = 1005;
bitset<maxn> b[maxn];
int main()
{
  int n, m,x,y,ans;
  ans = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; i++)//自己能到自己,这个必须初始化,否则后序 | 运算会出错.
  {
    b[i][i] = 1;
  }
  while (m--)//初始化
  {
    cin >> x >> y;
    b[x][y] = 1;
  }
  for (int i = 1; i <= n; i++)//遍历
  {
    for (int j = 1; j <= n; j++)
    {
      if (b[j][i])
      {
        b[j] = b[i] | b[j];
      }
      //if (b[i][j])//为啥我这样写不可以呢? 画图之后隐隐约约感觉不该这样写..具体还不知道为啥.
      //{
      //  b[i] = b[i] | b[j];// 
      //}
    }
  }
  for (int i = 1; i <= n; i++)
  {
    ans +=b[i].count();//统计已知所有关系
  }
  cout << n * (n - 1) / 2 - (ans - n);//记得最后:所有的关系-(ans-n),因为实际所有关系中,自己到自己忽略,不应计数.
  return 0;
}


心得收获


1.bitset的使用

2.代码中加注释的那部分为啥不行,我还存在疑惑,大佬们可以帮忙解答下.

相关文章
[USACO 2021.02 Feb]Problem 2. Comfortable Cows
[USACO 2021.02 Feb]Problem 2. Comfortable Cows
LeetCode 70. Climbing Stairs
你正在爬楼梯。 它需要n步才能达到顶峰。 每次你可以爬1或2步。 您可以通过多少不同的方式登顶? 注意:给定n将是一个正整数。
59 0
LeetCode 70. Climbing Stairs
|
人工智能 BI
AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)
AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)
133 0
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
96 0
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
115 0
|
人工智能
Educational Codeforces Round 33
A. Chess For Three time limit per test1 second memory limit per test256 megabytes inputstanda...
1169 0
|
人工智能
Educational Codeforces Round 31 A B C
A. Book Reading time limit per test2 seconds memory limit per test256 megabytes inputstandard...
1110 0