题意：
from mhy12345
给你一个满流网络，对于每一条边，压缩容量1 需要费用ai，扩展容量1 需要bi，
当前容量上限ci，每单位通过该边花费di，限制网络流量不能改变。调整后必须满 流，设调整了K 次，使得费用减少量为D，最大化D/K就是给你一个费用流，但不是最小，增广的费用为b+d，退流的费用为a-d
就是正反向增广路
根据消圈定理，流f为mcmf当且仅当无负费用增广圈
01分数规划+spfa求负环即可
#include#include #include #include #include using namespace std;typedef long long ll;#define fir first#define sec secondconst int N = 505, M = 1e4+5, mo = 1e9+7;inline int read() { char c=getchar(); int x=0,f=1; while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} return x*f;}int n, m;double l, r;struct edge {int v, ne; double w;} e[M];int cnt, h[N];inline void ins(int u, int v, double w) { e[++cnt] = (edge) {v, h[u], w}; h[u] = cnt;}namespace nc { int vis[N], T; double d[N]; bool dfs(int u, double mid) { vis[u] = T; for(int i=h[u]; i; i=e[i].ne) { int v = e[i].v; double w = e[i].w + mid; if(d[v] > d[u] + w) { d[v] = d[u] + w; if(vis[v] == T || dfs(v, mid)) return true; } } vis[u] = 0; return false; } bool neg_circle(double mid) { memset(vis, 0, sizeof(vis)); memset(d, 0, sizeof(d)); for(T=1; T<=n+2; T++) if(dfs(T, mid)) return true; return false; }}bool check(double mid) { return nc::neg_circle(mid);}int main() { freopen("in", "r", stdin); n = read(); m = read(); for(int i=1; i<=m; i++) { int u = read(), v = read(), a = read(), b = read(), c = read(), d = read(); ins(u, v, b+d); if(c) ins(v, u, a-d); r += c * d; } while(r - l > 1e-3) { double mid = (l+r)/2.0; if(check(mid)) l = mid; else r = mid; } printf("%.2lf\n", l);}