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=1010; const int INF=0x3f3f3f3f; inline int in(){ int x=0;char ch=getchar(); while(ch>'9' || ch<'0') ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } struct Node{ int data,next,low; }node[maxn*maxn*2]; #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=0;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,-1,sizeof(dis)); int H=0,T=1;que[1]=s,dis[s]=0; while(H<T){ H++; for(int point=head[que[H]];point!=-1;point=then) if(www && dis[now]<0){ dis[now]=dis[que[H]]+1; que[++T]=now; } } if(dis[t]<0) return false; return true; } int dfs(int x,int low){ if(x==t) return low; int Low; for(int &point=cur[x];point!=-1;point=then) if(www && dis[now]==dis[x]+1){ Low=dfs(now,min(low,www)); if(Low){ www-=Low;node[point^1].low+=Low; return Low; } } return 0; } int main(){ #ifndef ONLINE_JUDGE freopen("2039.in","r",stdin); freopen("2039.out","w",stdout); #endif scanf("%d",&n); t=n+1; for(int i=s;i<=t;i++) head[i]=-1; for(int i=1;i<=n;i++) cost[i]=in(),add(i,t,cost[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=in(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ stoi[i]+=a[i][j]; stoi[j]+=a[i][j]; if(a[i][j]) add2(i,j,a[i][j]<<1); } for(int i=1;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(1){ flag=dfs(s,INF); if(!flag) break; ans-=flag; } } printf("%d",ans); return 0; }