题解 P1791 【[国家集训队]人员雇佣】

斯德哥尔摩 · 2019-03-09 17:35:06 · 题解

P1791 [国家集训队]人员雇佣

卡常卡了好久终于过了。。。

于是补一发题解，给后来人一个借鉴。

记住：

1. 如果你的Dinic开了O2却TLE，请不要开O2。。。

2. 如果你的Dinic不开O2却还是TLE，请使用ISAP。。。

3. 如果你的ISAP开了O2却TLE，请不要开O2。。。

4. 如果你的ISAP不开O2却还是TLE，请使用HLPP。。。（当然我没用。。。）

以上是我的个人做题总结。。。

可以与看一下我的提交记录。

在BZOJ上Dinic是可以过的。

下面说解法：

显然这是一个最小割模型。

类似的题目有这题和这题。

对于本题，我们设<u,v,w>表示从u到v，流量为w得一条有向边，当然包括流量为零的反向边。

将源点设为S，汇点设为T。

于是连边：<S,x,\sum_{i=1}^nE_{x,i}>,<x,T,A_x>

那个敌对公司的影响先不管它。

这样，跑最小割即可。

也就是：

割掉S到x的边表示不雇佣这个人并且不给它工资，收益也被丢掉。

割掉x到T的边表示雇佣这个人并且给它工资。

然后用总收益Sum减去最小割Ans即为答案。

然后考虑敌对公司：

我们发现选这一对i,j和不选i,j之间的收益差正好是E_{i,j}\times 2。

所以我们对于每对i,j连边<i,j,E_{i,j}\times 2>。

然后同上，跑最小割即可。

这个题就做完了。

记得开long\ long。