bzoj3130

这道题要谈很多；

首先，第一问等会我另外说一下；

第二问比较难想，首先我们的考虑两人的最优策略是什么

对于Bob，我们令分配了x条边的费用，则我们要最大化

ans=Σ(i=1 to x) flow[i] * p/x (flow[i]为选择的边）

显然ans<=x*maxflow[i]*p/x=maxflow[i]*p

显然ans最大的方案就是将费用全部分配到实际流量最大的那条边上去

这样Alice的方案也明确了，就是在维持最大流不变的前提下，是实际流量最大的那条边最小

对于这类最小化最大的问题，我们不难想到二分答案，二分网络流上界流量

但请注意，有没有从题目保留的精度想到什么呢？

对，这道题流量可以是实数，

对于任意实数的网络流是不可做的，但是在一定精度范围内就照样可行；

照样就没什么问题了

这里说下我发现我以前写的最大流sap是不够好的

没加当前弧优化，之前很多题没TLE真是万幸；

在bzoj2127（之后放在一个专题写）中体现的特别明显，如果只用sap+gap妥妥TLE

用了之后1s多跑完……

这里给出最终的最大流写法（sap+gap+cur）

 const inf=;

       ok=1e-6;  //控制精读

 type node=record

        next,point:longint;

        flow:double;

      end;

 var edge:array[..] of node;

     cur,numh,p,h,pre:array[..] of longint;

     w,x,y:array[..] of longint;

     d:array[..] of double;

     l,r,mid,ans1,ans2:double;

     t,len,i,n,m:longint;

 function min(a,b:double):double;

   begin

     if a>b then exit(b) else exit(a);

   end;

 procedure add(x,y:longint;f:double);

   begin

     inc(len);

     edge[len].flow:=f;

     edge[len].point:=y;

     edge[len].next:=p[x];

     p[x]:=len;

   end;

 function sap(k:double):double;  //带当前弧优化

   var u,i,j,tmp,q:longint;

       neck:double;

       flag:boolean;

   begin

     len:=-;

     fillchar(p,sizeof(p),);

     for i:= to m do

     begin

       add(x[i],y[i],min(k,w[i]));

       add(y[i],x[i],);

     end;

     fillchar(numh,sizeof(numh),);

     fillchar(h,sizeof(h),);

     numh[]:=n;

     u:=;

     neck:=inf;

     sap:=;

     cur:=p;

     while h[]<n do

     begin

       d[u]:=neck;

       flag:=false;

       i:=cur[u];

       while i<>- do

       begin

         j:=edge[i].point;

         if (edge[i].flow>) and (h[u]=h[j]+) then

         begin

           flag:=true;

           cur[u]:=i;

           pre[j]:=u;

           neck:=min(neck,edge[i].flow);

           u:=j;

           if u=n then

           begin

             sap:=sap+neck;

             while u<> do

             begin

               u:=pre[u];

               j:=cur[u];

               edge[j].flow:=edge[j].flow-neck;

               edge[j xor ].flow:=edge[j xor ].flow+neck;

             end;

             neck:=inf;  //勿忘1

           end;

           break;

         end;

         i:=edge[i].next;

       end;

       if not flag then

       begin

         dec(numh[h[u]]);

         if numh[h[u]]= then exit;

         tmp:=n;

         i:=p[u];

         q:=;

         while i<>- do

         begin

           j:=edge[i].point;

           if (tmp>h[j]) and (edge[i].flow>) then

           begin

             q:=i;

             tmp:=h[j];

           end;

           i:=edge[i].next;

         end;

         h[u]:=tmp+;

         cur[u]:=q;     //勿忘2

         inc(numh[h[u]]);

         if u<> then

         begin

           u:=pre[u];

           neck:=d[u];   //记录当前瓶颈边的作用

         end;

       end;

     end;

   end;

 begin

   readln(n,m,t);

   for i:= to m do

   begin

     readln(x[i],y[i],w[i]);

     if r<w[i] then r:=w[i];

   end;

   l:=;

   ans1:=sap(r);

   while r-l>ok do   //实数范围内的二分答案

   begin

     mid:=(l+r)/;

     if abs(ans1-sap(mid))<ok then r:=mid

     else l:=mid;

   end;

   writeln(ans1::);

   writeln(r*t::);

 end.

巴特西

bzoj3130

最新文章

热门文章