3597: [Scoi2014]方伯伯运椰子

题意：

from mhy12345

给你一个满流网络，对于每一条边，压缩容量1 需要费用ai，扩展容量1 需要bi，

当前容量上限ci，每单位通过该边花费di，限制网络流量不能改变。调整后必须满

流，设调整了K 次，使得费用减少量为D，最大化D/K

---

就是给你一个费用流，但不是最小，增广的费用为b+d，退流的费用为a-d

就是正反向增广路

根据消圈定理，流f为mcmf当且仅当无负费用增广圈

01分数规划+spfa求负环即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

#define fir first

#define sec second

const 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);

}