P2881 [USACO07MAR]Ranking the Cows G

P2881 [USACO07MAR]Ranking the Cows G

题目描述

FJ想按照奶牛产奶的能力给她们排序。现在已知有N头奶牛（1 ≤ N ≤ 1,000）。FJ通过比较，已经知道了M（1 ≤ M ≤ 10,000）对相对关系。每一对关系表示为“X Y”，意指X的产奶能力强于Y。现在FJ想要知道，他至少还要调查多少对关系才能完成整个排序。

输入格式

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.

输出格式

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

题目分析

这个题主要考察图的应用.
我们可以把牛头数作为图的结点,把产奶能力作为图中的关系,可以做下图所示的转换:

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

可以利用bitset 位运算 ，每个结点用一个bitset表示。具体如何使用可以点击这里
bitsetp[maxn];-

1. 建立一个 位数的二进制数组。
2. 初始化时，p[i][i]=1, 即p[i]的第i位为1. 也就是自己能推出自己.
3. 输入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
4. 判断每个数组的每一位:
   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.代码中加注释的那部分为啥不行,我还存在疑惑,大佬们可以帮忙解答下.