BZOJ3597 SCOI2014 Coconut

目标    Maximise λ = 

    g(λ)=

 DAY2 T1：比较裸的分数规划

 很容易想到先二分答案判断可行

 我们直接把加流量的操作视为反边，减流量的操作视为正边，那么验证答案是否可行就是在找一个负环。

 假如当前二分的答案为K，那这条边正边(加流量)就是ui通向vi，代价为bi+wi+K，负边（减流量）就是vi通向ui，代价  ai+K-wi，

 然后随便跑个算法判断负环就可以了。唯一要注意的是流量为0的边无法再减流量了。

 考场上得了90分，有个点WA了，和答案相差很远，原因不详。。。

 第一题一眼分数规划，加大一条边流量1的费用为b+w，减小流量1的费用为a-w

 然后按这个建图，如果有负环那么沿着这条路走不回减小流量，但是会减小费用

 减小多少就是这个环的权值和，然后要让平均每条边的费用最大...

然后DFS的SPFA太神了不会写orzzz

program bzoj3597;

type tnode=record
        n,ow,next:longint;
        w:extended;
     end;

const inf=1e43;
      maxn=517;
      maxm=10017;
      maxw=1017;

var g,q,enq:array[0..maxn] of longint;
    d:array[0..maxn] of extended;
    v:array[0..maxn] of boolean;
    mem:array[0..maxm] of tnode;
    n,m,memsize,frt,rer:longint;

procedure insnbs(u,v,iw:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; ow:=iw; next:=g[u];
end; g[u]:=memsize;
end;

function spfa(u:longint):boolean;
var head,tail,t1:longint;
begin
frt:=0; rer:=1; q[1]:=u; v[u]:=true; enq[u]:=1; d[u]:=0;
while frt<>rer do begin
        frt:=frt mod maxn+1; head:=q[frt]; t1:=g[head];
        while t1<>0 do begin
                tail:=mem[t1].n; if d[head]+mem[t1].w<d[tail] then begin
                        d[tail]:=d[head]+mem[t1].w; if not v[tail] then begin
                                rer:=rer mod maxn+1; q[rer]:=tail; v[tail]:=true;
                                inc(enq[tail]); if enq[tail]>n+2 then exit(true);
                        end;
                end; t1:=mem[t1].next;
        end; v[head]:=false;
end; exit(false);
end;

procedure makegraph(lambda:extended);
var i:longint;
begin
fillchar(enq,sizeof(enq),0); fillchar(v,sizeof(v),0);
for i:=1 to n+2 do d[i]:=inf;
for i:=1 to memsize do mem[i].w:=mem[i].ow+lambda;
end;

procedure init;
var i,u,v,a,b,c,w:longint;
begin
fillchar(g,sizeof(g),0); memsize:=0;
readln(n,m); for i:=1 to m do begin
        readln(u,v,a,b,c,w);
        if (u=n+1)or(v=n+1) then continue;
        insnbs(u,v,b+w); if c>0 then insnbs(v,u,a-w);
end;
end;

function ans:extended;
var l,r,mid:extended;
begin
l:=0; r:=maxw; while r-l>1e-4 do begin
        mid:=(l+r)/2; makegraph(mid);
        if spfa(n+2) then l:=mid else r:=mid;
end; exit(l);
end;

begin
init;
writeln(ans:0:2);
end.