题解 P1791 【[国家集训队]人员雇佣】
斯德哥尔摩
2019-03-09 17:35:06
[P1791 [国家集训队]人员雇佣](https://www.luogu.org/problemnew/show/P1791)
卡常卡了好久终于过了。。。
于是补一发题解，给后来人一个借鉴。
记住：
1. 如果你的$Dinic$开了$O2$却$TLE$，请不要开$O2$。。。
2. 如果你的$Dinic$不开$O2$却还是$TLE$，请使用$ISAP$。。。
3. 如果你的$ISAP$开了$O2$却$TLE$，请不要开$O2$。。。
4. 如果你的$ISAP$不开$O2$却还是$TLE$，请使用$HLPP$。。。（当然我没用。。。）
以上是我的个人做题总结。。。
可以与看一下我的[提交记录](https://www.luogu.org/recordnew/lists?uid=49998&pid=P1791&status=&sort=0)。
在$BZOJ$上$Dinic$是可以过的。
## 下面说解法：
显然这是一个最小割模型。
类似的题目有[这题](https://www.cnblogs.com/Yangrui-Blog/p/10465922.html)和[这题](https://www.cnblogs.com/Yangrui-Blog/p/10464509.html)。
对于本题，我们设$<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$。
$Dinic$的代码在[我的博客](https://www.cnblogs.com/Yangrui-Blog/p/10502148.html)里。
各位巨佬也可以帮忙看看我的$Dinic$哪里写丑了。。。
附上$ISAP$的代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#define MAXN 1010
#define MAXM 2100000
#define MAX (1LL<<60)
using namespace std;
int n,c=2,s,t;
int head[MAXN],num[MAXN],deep[MAXN],h[MAXN];
long long sum=0;
struct Edge{
int next,to;
long long w;
}a[MAXM];
inline int read(){
int date=0;char c=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date;
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline void add(int u,int v,long long w){
a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
a[c].to=u;a[c].w=0;a[c].next=head[v];head[v]=c++;
}
long long dfs(int x,long long limit){
if(x==t)return limit;
int v;
long long sum,cost=0;
for(int i=h[x];i;i=a[i].next){
v=a[i].to;
if(a[i].w&&deep[v]+1==deep[x]){
sum=dfs(v,min(a[i].w,limit-cost));
a[i].w-=sum;
a[i^1].w+=sum;
cost+=sum;
if(cost==limit)return cost;
if(a[i].w)h[x]=i;
}
}
--num[deep[x]];
if(!num[deep[x]])deep[s]=n+2;
deep[x]++;num[deep[x]]++;
h[x]=head[x];
return cost;
}
long long ISAP(){
long long ans=0;
for(int i=1;i<=n;i++)h[i]=head[i];
while(deep[s]<n+2)ans+=dfs(s,MAX);
return ans;
}
void init(){
int x;
long long y;
n=read();
s=n+1;t=n+2;
for(int i=1;i<=n;i++){
x=read();
add(i,t,x);
}
for(int i=1;i<=n;i++){
y=0;
for(int j=1;j<=n;j++){
x=read();
y+=x;
add(i,j,x*2);
}
sum+=y;
add(s,i,y);
}
}
int main(){
init();
printf("%lld\n",sum-ISAP());
return 0;
}
```