人员雇佣
Time Limit: 20 Sec Memory Limit: 259 MB
[Submit][Status][Discuss]
Description
作为一个富有经营头脑的富翁，小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,（我们用Ei,j表示i经理对j经理的了解程度），即当经理i和经理j同时被雇佣时，经理i会对经理j做出贡献，使得所赚得的利润增加Ei,j。当然，雇佣每一个经理都需要花费一定的金钱Ai，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小L当然不会雇佣他。 然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少Ei,j（注意：这里的Ei,j与上面的Ei,j 是同一个）。 作为一个效率优先的人，小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗？
Input
第一行有一个整数N<=1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱 接下来的N行中一行包含N个数，表示Ei,j，即经理i对经理j的了解程度。（输入满足Ei,j=Ej,i）
Output
第一行包含一个整数，即所求出的最大值。
Sample Input
3 5 100
0 6 1
6 0 2
1 2 0
Sample Output
HINT
50%的数据中 N<=100
100%的数据中 N<=1000 , Ei,j<=maxlongint , Ai<=maxlongint
Main idea
给定若干关系，选择一个人需要固定的费用，对于i,j，选择了其中一个则损失E[i][j]，两个都选了则获得2*E[i][j]，问能获得的最大价值。
Solution
显然就是一个最小割的模型，我们直接套用论文里面的模型即可。
针对于这道题，我们对于代价建图，用Ans=总和-最小代价即可。
对于第i个点，如果选了，会损失a[i]，连边(S,i,a[i])：表示选了它之后的代价；如果不选，会损失ΣE[i][j]，所以连边(i,T,ΣE[i][j])，表示不选的损失。
然后对于一对点i,j，连边(i,j,2*E[i][j])，表示如果不选i,选了j的话，本来i中选j的利益得不到，又要损失j对i的影响为E[i][j]，一共损失了2*E[i][j]。
然后求一下最小割即可。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
using namespace std; typedef long long s64;
const int ONE=;
const s64 INF=; int n,x;
s64 res;
int tou,wei,S,T;
int Dep[ONE],q[],E[ONE];
int next[ONE],first[ONE],go[ONE],tot;
s64 w[ONE];
s64 Ans; int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} int Add(int u,int v,s64 z)
{
next[++tot]=first[u]; first[u]=tot; go[tot]=v; w[tot]=z;
next[++tot]=first[v]; first[v]=tot; go[tot]=u; w[tot]=;
} int Bfs()
{
memset(Dep,,sizeof(Dep));
tou=; wei=;
q[]=S; Dep[S]=;
for(int i=S;i<=T;i++) E[i]=first[i];
while(tou<wei)
{
int u=q[++tou];
for(int e=first[u];e;e=next[e])
{
int v=go[e];
if(Dep[v] || !w[e]) continue;
Dep[v]=Dep[u]+;
q[++wei]=v;
}
}
return (Dep[T]>);
} s64 Dfs(int u,s64 Limit)
{
if(u==T || !Limit) return Limit;
s64 from=,f;
for(int &e=E[u];e;e=next[e])
{
int v=go[e];
if(Dep[v]!=Dep[u]+ || !w[e]) continue;
f=Dfs(v,min(Limit,w[e]));
w[e]-=f;
w[((e-)^)+]+=f;
Limit-=f;
from+=f;
if(!Limit) break;
}
return from;
} int main()
{
n=get();
S=; T=n+;
for(int i=;i<=n;i++)
{
x=get();
Add(S,i,x);
} for(int i=;i<=n;i++)
{
res=;
for(int j=;j<=n;j++)
{
x=get();
res+=x; Ans+=x;
Add(i,j,*x);
}
Add(i,T,res);
} while(Bfs()) Ans-=Dfs(S,INF); printf("%lld",Ans); }