题意：
有N个经理，Ei,j表示i经理对j经理的了解程度，当经理i和经理j同时被雇佣时，利润增加Ei,j*2。同时，雇佣每一个经理都需要花费一定的金钱Ai。没有被雇佣的人会被竞争对手所雇佣，使得所赚得的利润减少Ei,j（意思是经理i和j如果只雇佣一个，就会少Ei,j，如果两个都没被雇佣就不扣钱）。求最大利润。N≤1000
题解：
S集表示雇佣，T集表示不雇佣。每个经理拆成x，y两点。s向所有x点连，流量为雇佣费用。对于每个Ei,j，i，j经理连一条流量为2*Ei,j的无向边，同时i和j都向t连流量为Ei,j的边，最小割为所有Ei,j*2减最大流。由于边数大，需要合并一下边。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define maxn 1100 6 #define inc(i,j,k) for(int i=j;i<=k;i++) 7 #define INF 1000000000000000000 8 #define ll long long 9 using namespace std; 10 11 struct e{int t;ll c;int n;}; e es[maxn*2000]; int g[maxn],ess; 12 inline void pe(int f,int t,ll c){ 13 es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess; 14 } 15 inline void pe2(int f,int t,ll c){ 16 es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,c,g[t]}; g[t]=ess; 17 } 18 inline void init(){ 19 ess=-1; memset(g,-1,sizeof(g)); 20 } 21 queue <int> q; int h[maxn]; 22 bool bfs(int s,int t){ 23 memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s); 24 while(! q.empty()){ 25 int x=q.front(); q.pop(); 26 for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t); 27 } 28 return h[t]!=-1; 29 } 30 ll dfs(int x,int t,ll f){ 31 if(x==t)return f; ll u=0; 32 for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){ 33 ll w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u; 34 } 35 if(u==0)h[x]=-1; return u; 36 } 37 ll dinic(int s,int t){ 38 ll f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f; 39 } 40 int n,s,t; ll a[maxn],b,tot; 41 int main(){ 42 scanf("%d",&n); s=0; t=n+1; init(); inc(i,1,n)scanf("%lld",&b),pe(s,i,b); memset(a,0,sizeof(a)); 43 inc(i,1,n)inc(j,1,n){ 44 scanf("%lld",&b); if(i>j||b==0)continue; a[i]+=b; a[j]+=b; pe2(i,j,2*b); tot+=2*b; 45 } 46 inc(i,1,n)pe(i,t,a[i]); printf("%lld",tot-dinic(s,t)); return 0; 47 }
20160530