首先很容易看出这是一个带上下界的网络流题...
源点向代表每一行的点连边，代表每一列的点向汇点连边
每一行向每一列连边，连的边就如前面无源汇可行流一样
然后由于求的是最大流，二分答案
每次从t→s连一条下限为mid的边
问题来了..最后要输出的和最终的mid有什么关系呢...
我们考虑这张图上的流量代表什么
我们连的边代表的刚开始没有考虑下限的边所以认为是波动的数值
然而实际上很简单就是每个格子的数值
最后输出的答案是整张图的数值
每个点在自己位置、行末和列末各统计一次
所以乘上3输出就可以了
因为INF设得过小WA了两次...
program zoj2314;
const maxn = ;maxm = ;INF = ;
var fa,next,ter,w,rec,flow:array[-..maxm]of longint;
link,dis,opt,inp:array[-..maxn]of longint;
vis:array[-..maxn]of boolean;
n,m,e,tt,test,i,s,t,x,y,l,r,j,mid,sum,lx,rx,ans:longint;
a:array[-..maxn,-..maxn]of extended; function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end; function spfa:boolean;
var head,tail,x,j:longint;
begin
fillchar(vis,sizeof(vis),true);
fillchar(dis,sizeof(dis),);
head:=;tail:=;opt[]:=s;vis[s]:=false;dis[s]:=;
while head<>tail do
begin
head:=(head+) mod maxn;
x:=opt[head];j:=link[x];
while j<> do
begin
if (dis[x]+<dis[ter[j]])and(w[j]>) then
begin
dis[ter[j]]:=dis[x]+;
if vis[ter[j]] then
begin
vis[ter[j]]:=false;
tail:=(tail+) mod maxn;
opt[tail]:=ter[j];
end;
end;
j:=next[j];
end;
vis[x]:=true;
end;
if dis[t]<>dis[t+] then exit(true) else exit(false);
end; function dfs(p,sum:longint):longint;
var tem,j,x:longint;
begin
tem:=;
if p=t then exit(sum);
j:=link[p];
while j<> do
begin
if (dis[ter[j]]=dis[p]+)and(w[j]>) then
begin
x:=dfs(ter[j],min(sum-tem,w[j]));
inc(tem,x);dec(w[j],x);inc(w[rec[j]],x);
if rec[j]=j+ then inc(flow[fa[j]],x) else dec(flow[fa[rec[j]]],x);
if tem=sum then exit(sum);
end;
j:=next[j];
end;
exit(tem);
end; procedure add(x,y,z:longint);
begin
inc(e);ter[e]:=y;next[e]:=link[x];link[x]:=e;w[e]:=z;rec[e]:=e+;
inc(e);ter[e]:=x;next[e]:=link[y];link[y]:=e;w[e]:=;rec[e]:=e-;
end; function Jud:boolean;
var j:longint;
begin
j:=link[s];
while j<> do
begin
if w[j]> then exit(false);
j:=next[j];
end;
exit(true);
end; function Solve:boolean;
var i,sum:longint;
begin
sum:=;
while spfa do inc(sum,dfs(s,));
if (not Jud) then exit(false) else exit(true);
end; begin
readln(n);ans:=;
for i:= to n do
begin
for j:= to n do begin read(a[i,j]);inc(ans,trunc(a[i,j]));end;
readln;
end;
Lx:=;Rx:=;sum:=-;
while Lx<=Rx do
begin
mid:=(Lx+Rx) >> ;
fillchar(next,sizeof(next),);
fillchar(link,sizeof(link),);
fillchar(inp,sizeof(inp),);
e:=;s:= ;t:=*n+;
for i:= to n- do
begin
l:=trunc(a[i,n]);
if a[i,n]<>l then add(s,i,);
dec(inp[s],l);inc(inp[i],l); l:=trunc(a[n,i]);
if a[n,i]<>l then add(n+i,t,);
dec(inp[n+i],l);inc(inp[t],l);
end;
for i:= to n- do
for j:= to n- do
begin
l:=trunc(a[i,j]);
if a[i,j]<>l then add(i,n+j,);
dec(inp[i],l);inc(inp[n+j],l);
end;
add(t,s,INF);
inc(inp[s],mid);dec(inp[t],mid);
dec(s);inc(t);
for i:=s+ to t- do
if inp[i]> then add(s,i,inp[i]) else
if inp[i]< then add(i,t,-inp[i]);
if Solve then begin sum:=mid;Lx:=mid+ end else Rx:=mid-;
end;
writeln(sum*);
end.