题目描述
输出格式
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];-
建立一个 位数的二进制数组。
初始化时,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.代码中加注释的那部分为啥不行,我还存在疑惑,大佬们可以帮忙解答下.