把这个式子弄清楚就知道这是最小割了

相当于，选某个点i有收入ai,i，会损失ci,

如果i,j都被选则有额外收入ai,j+aj,i

明显，对每个点i，连(s,i,∑ai,j) (i,t,ci)

对每对i,j连边(i,j,ai,j)，没了

1 const inf=100000007;  2 type node=record  3        po,next,flow:longint;  4      end;  5   6 var e:array[0..2000010] of node;  7     p,numh,h,cur,pre,d:array[0..510] of longint;  8     t,len,ans,i,j,n,m,x,s:longint;  9  10 procedure add(x,y,f:longint); 11   begin 12     inc(len); 13     e[len].po:=y; 14     e[len].flow:=f; 15     e[len].next:=p[x]; 16     p[x]:=len; 17   end; 18  19 procedure build(x,y,f:longint); 20   begin 21     add(x,y,f); 22     add(y,x,0); 23   end; 24  25 function min(a,b:longint):longint; 26   begin 27     if a>b then exit(b) else exit(a); 28   end; 29  30 function sap:longint; 31   var u,i,j,tmp,neck,q:longint; 32   begin 33     numh[0]:=t+1; 34     for i:=0 to t do 35       cur[i]:=p[i]; 36     u:=0; sap:=0; neck:=inf; 37     while h[0]
      
       -1 do 42       begin 43         j:=e[i].po; 44         if (e[i].flow>0) and (h[u]=h[j]+1) then 45         begin 46           neck:=min(neck,e[i].flow); 47           pre[j]:=u; 48           cur[u]:=i; 49           u:=j; 50           if u=t then 51           begin 52             sap:=sap+neck; 53             while u<>0 do 54             begin 55               u:=pre[u]; 56               j:=cur[u]; 57               dec(e[j].flow,neck); 58               inc(e[j xor 1].flow,neck); 59             end; 60             neck:=inf; 61           end; 62           break; 63         end; 64         i:=e[i].next; 65       end; 66       if i=-1 then 67       begin 68         dec(numh[h[u]]); 69         if numh[h[u]]=0 then break; 70         q:=-1; 71         tmp:=t; 72         i:=p[u]; 73         while i<>-1 do 74         begin 75           j:=e[i].po; 76           if e[i].flow>0 then 77             if tmp>h[j] then 78             begin 79               q:=i; 80               tmp:=h[j]; 81             end; 82           i:=e[i].next; 83         end; 84         h[u]:=tmp+1; 85         inc(numh[h[u]]); 86         cur[u]:=q; 87         if u<>0 then 88         begin 89           u:=pre[u]; 90           neck:=d[u]; 91         end; 92       end; 93     end; 94   end; 95  96 begin 97   len:=-1; 98   fillchar(p,sizeof(p),255); 99   readln(n);100   t:=n+1;101   for i:=1 to n do102   begin103     s:=0;104     for j:=1 to n do105     begin106       read(x);107       s:=s+x;108       build(i,j,x);109     end;110     build(0,i,s);111     ans:=ans+s;112   end;113   for i:=1 to n do114   begin115     read(x);116     build(i,t,x);117   end;118   writeln(ans-sap);119 end.