AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2039
鉴于一开始看题如果不仔细是看不懂题目的，还是说一下题目大意
[题目大意]：给定n个人，每个人有一个佣金，i和j如果同时被雇佣会产生2*E(i,j)的效益，i和j如果一个被雇佣一个不被雇佣会产生E(i,j)的亏损，求最大收益
[题目分析]：
发现这题和往常某道实验的题很像。[见网络流24题-太空飞行计划问题]
"很像"是说，如果没有“一个被雇佣一个不被雇佣”的惩罚的话一模一样。
那么先不考虑惩罚，那么就是直接往每个E[i][j]连边，容量为2*E[i][j]，然后E[i][j]往i,j连边，容量为INF，然后每个i往t连边，容量为cost[i]。
这样的话，割集就代表了一组决策，最小割为一组费用。最后的答案就是sigma(E[i][j])-maxflow。
现在我们考虑惩罚的部分怎么弄。
我们需要设计一种方案，使得如果选择两个能得到2*效益，选择一个会失去1*效益。
于是可以从s向每个i连边，容量为E[i][j]，然后在i与j之间连一条双向边，容量为2*E[i][j]。
这样的话，如果假设i选了，j没选，那么说明到i的流量会通过2*E[i][j]这条边再从cost[j]这条边流走，损失了2*E[i][j]，然后通过s->i的E[i][j]的补充，就完成了损失E[i][j]的操作。
假设i,j都选了，那么中间的边就只是一个调控流量的东西，使得i,j到t的流量都流满。
如果你发现这样打了速度不够快？...居然有人200ms能过，怎么我tm要用7000ms?下面有一些优化方法。
1.连两条单向边改成连一条来回流量都为w的边[可以减少边的数量]
2.读入优化
3.特判，数据中有许多E[i][j]=0的情况，这种情况你不要连边就好。
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; const int maxn=;
const int INF=0x3f3f3f3f; inline int in(){
int x=;char ch=getchar();
while(ch>'' || ch<'') ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return x;
} struct Node{
int data,next,low;
}node[maxn*maxn*]; #define now node[point].data
#define then node[point].next
#define www node[point].low int n,cnt,s,t,ans;
int head[maxn],cur[maxn];
int dis[maxn],que[maxn];
int stoi[maxn];
int a[maxn][maxn],cost[maxn]; void add(int u,int v,int w){
node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;
node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=;head[v]=cnt++;
} void add2(int u,int v,int w){
node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;
node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=w;head[v]=cnt++;
} bool BFS(){
memset(dis,-,sizeof(dis));
int H=,T=;que[]=s,dis[s]=;
while(H<T){
H++;
for(int point=head[que[H]];point!=-;point=then)
if(www && dis[now]<){
dis[now]=dis[que[H]]+;
que[++T]=now;
}
}
if(dis[t]<) return false;
return true;
} int dfs(int x,int low){
if(x==t) return low;
int Low;
for(int &point=cur[x];point!=-;point=then)
if(www && dis[now]==dis[x]+){
Low=dfs(now,min(low,www));
if(Low){
www-=Low;node[point^].low+=Low;
return Low;
}
}
return ;
} int main(){
#ifndef ONLINE_JUDGE
freopen("2039.in","r",stdin);
freopen("2039.out","w",stdout);
#endif scanf("%d",&n);
t=n+;
for(int i=s;i<=t;i++) head[i]=-;
for(int i=;i<=n;i++)
cost[i]=in(),add(i,t,cost[i]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
a[i][j]=in(); for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++){
stoi[i]+=a[i][j];
stoi[j]+=a[i][j];
if(a[i][j])
add2(i,j,a[i][j]<<);
} for(int i=;i<=n;i++)
add(s,i,stoi[i]),ans+=stoi[i]; int flag;
while(BFS()){
for(int i=s;i<=t;i++) cur[i]=head[i];
while(){
flag=dfs(s,INF);
if(!flag) break;
ans-=flag;
}
} printf("%d",ans);
return ;
}