BZOJ 2039 [2009 国家集训队]employ 人员雇佣

发布于 2017-05-26  92 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2039

题意:n 个人,雇佣每个人有一个费用,同时雇佣 (i,j) 收益为 2*E[i][j],只雇佣其中一个费用为 E[i][j],求最大总收益...


建模太神了... 怎么回事啊怎么回事啊还是学不会啊学不会啊怎么办啊怎么办啊...

  1. 每个人向汇点连一条权值为个人费用的边
  2. 对于两人中只雇佣一个人的费用 E[i][j],从源点向每个人连过去...
  3. 对于同时雇佣两人的收益 2*E[i][j],在 i,j 两人间连一条双向边

这么搞后一组割对应一组雇佣方案了,为什么呢,我们稍微想一想... 对于两个人 (i,j),他们的状态只有都雇佣,雇一个,都不雇三种,对于第一种,它的割是割断 (1),费用即为 cost[i]+cost[j],对于第二种,割断 (3) 后割断一对 (1),(2),第三种割断 (2)... 恰好覆盖了所以可能的割...

然而数据范围比较大,直接搞会 T,我们发现 (2) 连的边重边很多,我们处理一下,直接连总费用即可.... 代码如下:

对了.. 开 long long

 


一个非常弱的准退役OIER