我們的目標是使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.

轉載于:https://www.cnblogs.com/BLADEVIL/p/3500432.html

總結

以上是生活随笔為你收集整理的bzoj 3232 01分数规划+最大权封闭子图判定的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。