Luogu

分析

显然调整后总交通量不变是最佳的，因为不能减少，并且增加的话费用一定会变大。

发现压缩操作很像网络流中的退流，扩充操作很像网络流中的增广。

所以对于原图中的每条边 $(u,v,a,b,c,d)$ ，新建两条边：

• $v\to u$ ，边权为 $a-d$ （如果 $c=0$ ，不要建这条边）。对应压缩。
• $u\to v$ ，边权为 $b+d$ 。对应扩充。

发现在这张图跑，经过的边数就是调整次数 $k$ 。

所以调整后的新增费用就是 $\sum w$ 。

二分答案 $mid$ ，如果 $mid$ 合法那么显然有 $mid\geq \frac{X-Y}{k}$ ，也就是 $mid\times k > X-Y=X-(X+\sum w)=-\sum w$ 。

再移一次项，变为 $mid\times k+\sum w>0$ 。

于是将边权变为 $w+mid$ ，然后用 SPFA 找负环判断是否合法即可。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10;
const int M=6000+10;

int n,m;

struct Edge { int v,w,nxt; } e[M];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

double dis[N]; int cnt[N],inq[N];

inline int spfa(int s,double mid) {
    queue<int> Q; Q.push(s); dis[s]=cnt[s]=0,inq[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; double w=e[i].w+mid;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w,cnt[v]=cnt[u]+1;
                if (cnt[v]>=n+2) return 1;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return 0;
}

inline int check(double mid) { //是否存在负环
    for (re int i=1;i<=n+2;++i) dis[i]=inq[i]=cnt[i]=0;
    for (re int i=1;i<=n+2;++i)
        if (spfa(i,mid)) return 1;
    return 0;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),a=read(),b=read(),c=read(),d=read();
        if (u==n+1) a=b=d=0;
        if (c) addEdge(v,u,a-d); addEdge(u,v,b+d);
    }
    double L=0,R=1e8;
    while (R-L>1e-4) {
        double mid=(L+R)/2;
        if (check(mid)) L=mid;
        else R=mid;
    }
    printf("%.2lf\n",L);
    return 0;
}