把这个式子弄清楚就知道这是最小割了
相当于，选某个点i有收入ai,i，会损失ci,
如果i,j都被选则有额外收入ai,j+aj,i
明显，对每个点i，连(s,i,∑ai,j) (i,t,ci)
对每对i,j连边(i,j,ai,j)，没了
const inf=;
type node=record
po,next,flow:longint;
end; var e:array[..] of node;
p,numh,h,cur,pre,d:array[..] of longint;
t,len,ans,i,j,n,m,x,s:longint; procedure add(x,y,f:longint);
begin
inc(len);
e[len].po:=y;
e[len].flow:=f;
e[len].next:=p[x];
p[x]:=len;
end; procedure build(x,y,f:longint);
begin
add(x,y,f);
add(y,x,);
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function sap:longint;
var u,i,j,tmp,neck,q:longint;
begin
numh[]:=t+;
for i:= to t do
cur[i]:=p[i];
u:=; sap:=; neck:=inf;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=e[i].po;
if (e[i].flow>) and (h[u]=h[j]+) then
begin
neck:=min(neck,e[i].flow);
pre[j]:=u;
cur[u]:=i;
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(e[j].flow,neck);
inc(e[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=e[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then break;
q:=-;
tmp:=t;
i:=p[u];
while i<>- do
begin
j:=e[i].po;
if e[i].flow> then
if tmp>h[j] then
begin
q:=i;
tmp:=h[j];
end;
i:=e[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
cur[u]:=q;
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
t:=n+;
for i:= to n do
begin
s:=;
for j:= to n do
begin
read(x);
s:=s+x;
build(i,j,x);
end;
build(,i,s);
ans:=ans+s;
end;
for i:= to n do
begin
read(x);
build(i,t,x);
end;
writeln(ans-sap);
end.