网站建设的步骤过程,重庆建设信息,网站做多个产品,完整的网站优化放啊我们的目标是使v/c最小化#xff0c;所以构造函数g(x)v-x*c#xff0c;那么 二分一个X#xff0c;判断当时的v-x*c的值是多少#xff0c;然后根据g(x)函数的 单调递减性来二分#xff0c;判断#xff0c;直到g(x)0的时候当前的X就是答案。 然后我直接写的tle了#xff0…我们的目标是使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 BLADEVILconst 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 ab then min:b else min:a;end; function judge(x:extended):extended;begin if abs(x)lim then exit(0); if x0 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)*mj; for i:1 to n do for j:1 to m do begin read(key[i,j]); sum:sumkey[i,j]; end; for i:1 to n1 do for j:1 to m do read(heng[i,j]); for i:1 to n do for j:1 to m1 do read(shu[i,j]); source:num[n,m]2; sink:source1;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 ht do begin inc(h); cur:que[h]; q:last[cur]; while q0 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 psink 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 xsink then exit(flow); rest:flow; q:last[x]; while q0 do begin p:other[q]; if (judge(len[q])0) and (d[p]d[x]1) and (rest0) 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-llim do begin mid:(lr)/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 i1 then inc(cur,heng[i,j]); if in then inc(cur,heng[i1,j]); if j1 then inc(cur,shu[i,j]); if jm then inc(cur,shu[i,j1]); if cur0 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[i1,j],heng[i1,j]*mid); connect(num[i1,j],num[i,j],heng[i1,j]*mid); end; for i:1 to n do for j:1 to m-1 do begin connect(num[i,j],num[i,j1],shu[i,j1]*mid); connect(num[i,j1],num[i,j],shu[i,j1]*mid); end; ans:0; while bfs do ans:ansdinic(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
