题面

Sol

消圈定理：如果一个费用流网络的残量网络有负环，那么这个费用流不优

于是这个题就可以建出残量网络，然后分数规划跑负环了

# include 
    
     # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL int Input(){    RG int x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}const int maxn(6005);const double eps(1e-5);int n, m, first[maxn], cnt, vis[maxn];double dis[maxn], l = 0, r = 5e4;struct Edge{    int to, next;    double w;} edge[maxn];IL void Add(RG int u, RG int v, RG double w){    edge[cnt] = (Edge){v, first[u], w}, first[u] = cnt++;}IL int Dfs(RG int u, RG double w){    vis[u] = 1;    for(RG int e = first[u]; e != -1; e = edge[e].next){        RG int v = edge[e].to;        RG double d = dis[u] + edge[e].w + w;        if(dis[v] > d){            dis[v] = d;            if(vis[v] || Dfs(v, w)) return 1;        }    }    vis[u] = 0;    return 0;}IL int Check(RG double v){    for(RG int i = 1; i <= n + 2; ++i) dis[i] = 0, vis[i] = 0;    for(RG int i = 1; i <= n + 2; ++i) if(Dfs(i, v)) return 1;    return 0;}int main(){    n = Input(), m = Input();    for(RG int i = 1; i <= n + 2; ++i) first[i] = -1;    for(RG int i = 1; i <= m; ++i){        RG int u = Input(), v = Input(), a = Input(), b = Input(), c = Input(), d = Input();        Add(u, v, b + d);        if(c) Add(v, u, a - d);    }    while(r - l >= eps){        RG double mid = (l + r) / 2.0;        if(Check(mid)) l = mid;        else r = mid;    }    printf("%.2lf\n", r);    return 0;}