1 uses math;  2 var s,t,n,i,j,tot,w,cnt:longint;  3     last,pre,other,flow:array[0..2600000] of longint;  4     l,q:array[0..3000000] of longint;  5     ans:int64;  6 procedure insert(a,b,c,d:longint);  7 begin  8   pre[tot]:=last[a];  9   last[a]:=tot; 10   other[tot]:=b; 11   flow[tot]:=c; 12   inc(tot); 13   pre[tot]:=last[b]; 14   last[b]:=tot; 15   other[tot]:=a; 16   flow[tot]:=d; 17   inc(tot); 18 end; 19 function bfs:boolean; 20 var s1,t1,u,v,q1:longint; 21 begin 22   fillchar(q,sizeof(q),0); 23   for i:=0 to n do 24     l[i]:=-1; 25   s1:=0; 26   t1:=1; 27   l[s]:=1; 28   q[t1]:=s; 29   while (s1<t1) do 30   begin 31     inc(s1); 32     u:=q[s1]; 33     q1:=last[u]; 34     while (q1>=0) do 35     begin 36       v:=other[q1]; 37       if (flow[q1]>0) and (l[v]=-1) then 38       begin 39         inc(t1); 40         q[t1]:=v; 41         l[v]:=l[u]+1; 42       end; 43       q1:=pre[q1]; 44     end; 45   end; 46   if (l[t]=-1) then exit(false) else exit(true); 47 end; 48 function find(u,int:longint):longint; 49 var w,v,q1,t1:longint; 50 begin 51   if (u=t) then exit(int); 52   w:=0; 53   q1:=last[u]; 54   while (q1>=0) and (w<int) do 55   begin 56     v:=other[q1]; 57     if (l[v]=l[u]+1) then 58     begin 59       t1:=find(v,min(flow[q1],int-w)); 60       flow[q1]:=flow[q1]-t1; 61       flow[q1 xor 1]:=flow[q1 xor 1]+t1; 62       w:=w+t1; 63     end; 64     q1:=pre[q1]; 65   end; 66   if (w>=int) then l[u]:=-1; 67   exit(w); 68 end; 69 function dinic:int64; 70 var e:longint; 71   ans:int64; 72 begin 73   ans:=0; 74   while bfs do 75   begin 76     e:=find(s,maxlongint); 77     ans:=ans+e; 78   end; 79   exit(ans); 80 end; 81 begin 82   readln(n); 83   s:=n*n+n+1; 84   t:=n*n+n+2; 85   tot:=0; 86   for i:=0 to t do 87     last[i]:=-1; 88   cnt:=n; 89   ans:=0; 90   for i:=1 to n do 91   begin 92     for j:=1 to n do 93     begin 94       read(w); 95       inc(cnt); 96       insert(s,cnt,w,0); 97       insert(cnt,i,maxlongint,0); 98       if (i<>j) then insert(cnt,j,maxlongint,0); 99       ans:=ans+w;100     end;101     readln;102   end;103   for i:=1 to n do104   begin105     read(w);106     insert(i,t,w,0);107   end;108   readln;109   n:=t;110   writeln(ans-dinic);111 end.112   

 1 var n,i,j,s,ans,max,max1:longint; 2     b:array[0..1000,0..1000] of longint; 3     c,inc:array[0..1000] of longint; 4 begin 5   readln(n); 6   for i:=1 to n do 7   begin 8     for j:=1 to n do 9         read(b[i,j]);10     readln;11   end;12   for i:=1 to n do13     read(c[i]);14   readln;15   fillchar(inc,sizeof(inc),0);16   s:=0;17   ans:=0;18   for i:=1 to n do19   begin20     s:=0;21     for j:=1 to n do22         s:=s+b[i,j]+b[j,i];23     inc[i]:=b[i,i]-s+c[i];24   end;25   for i:=1 to n do26     for j:=1 to n do27         ans:=ans+b[i,j];28   for i:=1 to n do29     ans:=ans-c[i];30   while true do31   begin32     max:=-1;33     max1:=-1;34     for i:=1 to n do35       if (max<inc[i]) then36       begin37         max:=inc[i];38         max1:=i;39       end;40     if (max1=-1) then break;41     ans:=ans+max;42     for i:=1 to n do43       inc[i]:=inc[i]+b[i,max1]+b[max1,i];44     inc[max1]:=-1;45   end;46   writeln(ans);47 end.48     

 1 var t,l,n,m,i,j:longint; 2     a,f:array[0..1005,0..1005] of int64; 3 begin 4   readln(t); 5   for l:=1 to t do 6   begin 7     readln(n,m); 8     fillchar(a,sizeof(a),0); 9     fillchar(f,sizeof(f),0);10     for i:=1 to n do11     begin12       for j:=1 to m do13         read(a[i,j]);14       readln;15     end;16     for i:=1 to n do17         for j:=m downto 1 do18         begin19           f[i,j]:=f[i-1,j+1]+a[i,j];20           if (f[i-1,j]>f[i,j]) then f[i,j]:=f[i-1,j];21           if (f[i,j+1]>f[i,j]) then f[i,j]:=f[i,j+1];22         end;23     writeln(f[n,1]);24   end;25 end.