我们的目标是使v/c最小化，所以构造函数g(x)=v-x*c，那么
二分一个X，判断当时的v-x*c的值是多少，然后根据g(x)函数的
单调递减性来二分，判断，直到g(x)=0的时候当前的X就是答案。
然后我直接写的tle了，这是这两天tle的第3道题了。。。再改改。。。
/**************************************************************
Problem: 3232
User: BLADEVIL
Language: Pascal
Result: Time_Limit_Exceed
****************************************************************/
//By BLADEVIL
const
lim =1e-5;
var
n, m :longint;
pre, other :array[0..100010] of longint;
len :array[0..100010] of extended;
last :array[0..3010] of longint;
tot :longint;
num :array[0..60,0..60] of longint;
key, heng, shu :array[0..60,0..60] of longint;
sum :longint;
print :extended;
que, d :array[0..3010] of longint;
source, sink :longint;
function min(a,b:extended):extended;
begin
if a>b then min:=b else min:=a;
end;
function judge(x:extended):extended;
begin
if abs(x)<lim then exit(0);
if x<0 then exit(-1) else exit(1);
end;
procedure connect(x,y:longint;z:extended);
begin
inc(tot);
pre[tot]:=last[x];
last[x]:=tot;
other[tot]:=y;
len[tot]:=z;
end;
procedure init;
var
i, j :longint;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do num[i,j]:=(i-1)*m+j;
for i:=1 to n do
for j:=1 to m do
begin
read(key[i,j]);
sum:=sum+key[i,j];
end;
for i:=1 to n+1 do
for j:=1 to m do read(heng[i,j]);
for i:=1 to n do
for j:=1 to m+1 do read(shu[i,j]);
source:=num[n,m]+2;
sink:=source+1;
end;
function bfs:boolean;
var
q, p :longint;
h, t, cur :longint;
begin
fillchar(d,sizeof(d),0);
d[source]:=1;
h:=0; t:=1; que[1]:=source;
while h<t do
begin
inc(h);
cur:=que[h];
q:=last[cur];
while q<>0 do
begin
p:=other[q];
if (judge(len[q])>0) and (d[p]=0) then
begin
inc(t);
que[t]:=p;
d[p]:=d[cur]+1;
if p=sink then exit(true);
end;
q:=pre[q];
end;
end;
exit(false);
end;
function dinic(x:longint;flow:extended):extended;
var
rest, tmp :extended;
q, p :longint;
begin
if x=sink then exit(flow);
rest:=flow;
q:=last[x];
while q<>0 do
begin
p:=other[q];
if (judge(len[q])>0) and (d[p]=d[x]+1) and (rest>0) then
begin
tmp:=dinic(p,min(rest,len[q]));
rest:=rest-tmp;
len[q]:=len[q]-tmp;
len[q xor 1]:=len[q xor 1]+tmp;
end;
q:=pre[q];
end;
exit(flow-rest);
end;
procedure main;
var
l, r, mid :extended;
cur :longint;
ans :extended;
i, j :longint;
begin
l:=0; r:=90;
while r-l>lim do
begin
mid:=(l+r)/2;
fillchar(last,sizeof(last),0);
tot:=1;
for i:=1 to n do
for j:=1 to m do
begin
connect(source,num[i,j],key[i,j]);
connect(num[i,j],source,0);
end;
for i:=1 to n do
for j:=1 to m do
begin
cur:=0;
if i=1 then inc(cur,heng[i,j]);
if i=n then inc(cur,heng[i+1,j]);
if j=1 then inc(cur,shu[i,j]);
if j=m then inc(cur,shu[i,j+1]);
if cur>0 then
begin
connect(num[i,j],sink,cur*mid);
connect(sink,num[i,j],0);
end;
end;
for i:=1 to n-1 do
for j:=1 to m do
begin
connect(num[i,j],num[i+1,j],heng[i+1,j]*mid);
connect(num[i+1,j],num[i,j],heng[i+1,j]*mid);
end;
for i:=1 to n do
for j:=1 to m-1 do
begin
connect(num[i,j],num[i,j+1],shu[i,j+1]*mid);
connect(num[i,j+1],num[i,j],shu[i,j+1]*mid);
end;
ans:=0;
while bfs do
ans:=ans+dinic(source,maxlongint);
if judge(sum-ans)>0 then l:=mid else r:=mid;
end;
writeln(l:0:3);
end;
begin
init;
main;
end.