即在总流量不变的情况下调整每条边的流量。显然先二分答案变为求最小费用。容易想到直接流量清空跑费用流，但复杂度略有些高。
首先需要知道（不知道也行？）一种平时基本不用的求最小费用流的算法——消圈法。算法基于下面的定理：如果残量网络中有负环，当前费用流一定不是最小费用流（似乎很显然？）。注意到分数规划之后，我们需要知道的只是在调整边权后的网络里，最小费用流是否可能比原来更优，于是构造出残量网络，spfa判负环即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 5010 #define M 3010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } const double eps=1E-4; int n,m,p[N],t,q[N],cnt[N]; double dis[N]; bool flag[N]; struct data{int to,nxt;double len; }edge[M<<1]; void addedge(int x,int y,double z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;} int inc(int &x){x++;if (x>n+1) x-=n+1;return x;} bool spfa() { memset(flag,0,sizeof(flag)); memset(cnt,0,sizeof(cnt)); int head=0,tail=1;q[1]=n-1; for (int i=1;i<=n;i++) dis[i]=100000000;dis[n-1]=0; do { int x=q[inc(head)];flag[x]=0; for (int i=p[x];i;i=edge[i].nxt) if (dis[x]+edge[i].len<dis[edge[i].to]) { dis[edge[i].to]=dis[x]+edge[i].len; if (!flag[edge[i].to]) { flag[edge[i].to]=1; q[inc(tail)]=edge[i].to; cnt[edge[i].to]++; if (cnt[edge[i].to]>=n) return 1; } } }while (head!=tail); return 0; } bool check(double k) { for (int i=1;i<=t;i++) edge[i].len+=k; bool ans=spfa(); for (int i=1;i<=t;i++) edge[i].len-=k; return ans; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj3597.in","r",stdin); freopen("bzoj3597.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read()+2,m=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(),a=read(),b=read(),c=read(),d=read(); addedge(x,y,b+d); if (c>0) addedge(y,x,a-d); } double l=eps,r=10000,ans; while (l+eps<r) { double mid=(l+r)/2; if (check(mid)) ans=mid,l=mid+eps; else r=mid-eps; } printf("%.2f",ans); return 0; }