比较明显的网络流最小割模型，对于这种模型我们需要先求获利的和，然后减去代价即可。
我们对于第i个人来说， 如果选他，会耗费A[I]的代价，那么(source,i,a[i])代表选他之后的代价，如果不选他，我们会产生Σw[i][j] 1<=j<=n的代价，也就是这么多的利益我们无法得到，然后对于两个人的互相影响，连边(i,j,2*w[i][j])，代表如果不选i，选j的话，本来i中选j的利益得不到，又要损失j对i的影响为w[i][j]。所以共计损失2*w[i][j]。之后求最小割=最大流就行了。
/************************************************************** Problem: 2039 User: BLADEVIL Language: Pascal Result: Accepted Time:860 ms Memory:47112 kb****************************************************************///By
BLADEVILvar n
:longint; pre, other,
len
:array[0..4000010] of longint; last
:array[0..1010] of longint; l
:longint; source,
sink
:longint; que,
d
:array[0..1010] of longint; ans
:longint; function min(a,b:longint):longint;begin if
a>b then min:=b
else min:=a;end; procedure connect(x,y,z:longint);begin inc(l); pre[l]:=last[x]; last[x]:=l; other[l]:=y; len[l]:=z;end; procedure init;var i,
j
:longint; x
:longint; sum
:longint;begin read(n); source:=n+2; sink:=source+1; l:=1; for
i:=1 to n do begin read(x); connect(source,i,x); connect(i,source,0); end; for
i:=1 to n do begin sum:=0; for j:=1 to n do begin read(x); if x=0 then continue; sum:=sum+x; connect(i,j,x<<1); connect(j,i,0); ans:=ans+x; end; connect(i,sink,sum); connect(sink,i,0); end;end;function bfs:boolean;var h, t,
cur
:longint; q,
p
:longint;begin fillchar(d,sizeof(d),0); h:=0;
t:=1;
que[1]:=source; d[source]:=1; while
h<t do begin inc(h); cur:=que[h]; q:=last[cur]; while q<>0 do begin p:=other[q]; if (len[q]>0) and (d[p]=0) then begin inc(t); que[t]:=p; d[p]:=d[cur]+1; if p=sink then exit(true); end; q:=pre[q]; end; end; exit(false);end;function dinic(x,flow:longint):longint;var rest,
tmp
:longint; q,
p
:longint;begin if
x=sink then exit(flow); rest:=flow; q:=last[x]; while
q<>0
do begin p:=other[q]; if (len[q]>0) and (d[p]=d[x]+1) and (rest>0) then begin tmp:=dinic(p,min(len[q],rest)); dec(rest,tmp); dec(len[q],tmp); inc(len[q xor
1],tmp); end; q:=pre[q]; end; exit(flow-rest);end;procedure main;begin while
bfs do
ans:=ans-dinic(source,maxlongint div
10); writeln(ans);end;begin init; main;end.原文：http://www.cnblogs.com/BLADEVIL/p/3514711.html