题解 P1791 【[国家集训队]人员雇佣】
Freopen
2019-03-12 18:56:03
（我是不会告诉你们，在连边的时候判一下是不是0，是就不连边，就可以rank1。。。。。。）
这题就是一个网络流最小割在二元关系下求最大值的题。
先把矩阵中所有数加起来再减去我们构造的最小割就是最大值。
而最小割。
我们把每个人和S和T连边，割与S相连的边表示聘用，否则表示不聘用。那么一开始每个点与S相连的边的边权为b。
然后来考虑二元关系；
对于i，j，同时选的代价是0（我们一开始就加入了贡献）。
同时不选的代价是$E_{ij}+E{ji}$
一个选一个不选的代价是$E_{ij}+E{ji}+E{ij}$(需要减去一开始加的E)
通过（和其他二元关系一样的）解方程，我们可以得到i，j与S的连边流量为0，与T的连边流量为$E_{ij}$，i，j之间的连边流量为$2*E_{ij}$ 然后再把b加上去就行了。
AC Code(20190312 Rank1 72ms):
```cpp
#include<bits/stdc++.h>
#define maxn 1055
#define maxm maxn * maxn * 5
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct && (ct = (cs = cb) + fread(cb , 1 , 1<<15 , stdin),cs==ct)?0:*cs++)
void read(int &res)
{
char ch;bool f=0;
for(;!isdigit(ch=getc());) if(ch=='-') f=1;
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
(f) && (res = -res);
}
int n,S,T,tot;
int b[maxn];
LL sum[maxn],cap[maxm];
int dis[maxn];
int buf[maxn],info[maxn],Prev[maxm],to[maxm],cnt_e=1;
inline void Node(int u,int v,LL c){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v,cap[cnt_e]=c; }
inline void Line(int u,int v,LL c,LL d=0){ Node(u,v,c),Node(v,u,d); }
LL aug(int now,LL Max)
{
if(now == T) return Max;
LL inc , st = Max;
for(int &i=info[now];i;i=Prev[i])
if(cap[i] && dis[to[i]]+1 == dis[now])
{
inc = aug(to[i],min(cap[i] , st));
if(inc) st -= inc , cap[i] -= inc , cap[i^1] += inc;
else dis[to[i]] = 0;
if(!st) break;
}
return Max - st;
}
bool BFS()
{
static queue<int>q;
memset(dis,-1,sizeof dis);
q.push(T),dis[T]=0;
for(int now;!q.empty();)
{
now = q.front() , q.pop();
for(int i=info[now];i;i=Prev[i])
if(cap[i^1] && dis[to[i]]==-1)
{
dis[to[i]] = dis[now] + 1;
q.push(to[i]);
}
}
return dis[S] != -1;
}
int main()
{
read(n);
tot = n;
S = ++tot , T = ++tot;
LL ans = 0;
for(int i=1;i<=n;i++) read(b[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
read(x);
if(i<j && x)
{
ans += x*2;
sum[i] += x, sum[j] += x;
Line(i,j,x*2ll,x*2ll);
}
}
for(int i=1;i<=n;i++)
Line(S,i,b[i]),Line(i,T,sum[i]);
memcpy(buf,info,sizeof info);
for(;BFS();)
ans -= aug(S,inf),
memcpy(info,buf,sizeof buf);
printf("%lld\n",ans);
}
```