还是同一类最小割问题
对于只要记住，建图是来最小化损失，
最大化收益是所有收益-最小取不到的收益
首先对于每个经理i，如果不取，必然有signma(w[i,j])收益会得不到（这里我们先不考虑额外的损失）；
如果取，必然会损失a[i](其实这个也不是收益，只是我们最后用sum-mincut时，sum不包括a[i],就相当于损失了）；
下面考虑额外损失，对于i,j不在同一集合内（假设i被雇佣而j不被雇佣），会再损失2*w[i,j];
为什么是2倍呢，从建图来看，如果这样做最小割，雇佣i,不雇佣j,那么w[i,j]这个收益会被取到一次，而事实上不仅取不到还要额外损失，然后我们还要再减去一个经理之间的额外影响（由题意），所以是2倍；
然后分析完之后带入例子验证一下即可；
建图就不多说了
const inf=;
type node=record
next,flow,point:longint;
end; var edge:array[..] of node;
d,p,cur,pre,h,numh:array[..] of longint;
t,len,n,m,i,j,x,s,ans:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var neck,i,j,tmp,u,q:longint;
begin
numh[]:=t+;
sap:=;
neck:=inf;
for i:= to t do
cur[i]:=p[i];
u:=;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
cur[u]:=i;
pre[j]:=u;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
sap:=sap+neck;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
i:=p[u];
tmp:=t;
q:=-;
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[j]<tmp) then
begin
tmp:=h[j];
q:=i;
end;
i:=edge[i].next;
end;
cur[u]:=q;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
readln(n);
fillchar(p,sizeof(p),);
t:=n+;
for i:= to n do
begin
read(x);
add(i,t,x);
add(t,i,);
end;
for i:= to n do
begin
s:=;
for j:= to n do
begin
read(x);
s:=s+x;
if i<>j then
begin
add(i,j,x shl );
add(j,i,);
end;
end;
add(,i,s);
add(i,,);
ans:=ans+s;
end;
writeln(ans-sap);
end.