CF925F Parametric Circulation

根据无源汇上下界可行流的经典求法，令 \(f(t)=\sum\limits_{d_i> 0}d_i-\text{maxflow}\ge 0\)，则 \(f(t)=0\) 的时候有解。

根据最大流等于最小割，\(f(t)=\sum\limits_{d_i> 0}d_i-\text{mincut}\)。

我们考虑 \(\sum\limits_{d_i> 0}d_i=\sum\limits_{d_i<0}(-d_i)\)，所以 \(\sum\limits_{d_i>0}d_i\) 实际上是一个关于 \(t\) 的一次函数。

又因为每一个割集对应了一条直线，而最小割相当于对于这堆直线取 \(\min\)，所以 \(\text{mincut}\) 实际上是一个上凸函数，即二阶差分 \(\le 0\)。

于是合法的 \(t\) 相当于用一条直线去切一个上凸函数，得到的是一个连续的区间。

于是在值域内三分得到某个 \(f(t')=0\) 的 \(t'\)，再往两边二分即可得到 \(t\) 的取值范围。

理论复杂度有点大，但实际能过。

// Problem: Parametric Circulation
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF925F
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define pb pop_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<ll, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const ll inf = 1e18;
const int N = 1e3 + 100;
const int M = 2e3 + 200;
const int L = 1e8;

struct Flow {
	#define rz(x, y, z) x.resize(y + 5, z)
	int n, s, t, tot;
	struct edge { int to, nxt; ll w; };
	vector<int> hd, cr, d;
	vector<ll> deg;
	vector<edge> e;
	Flow () { }
	Flow (int _n) : n(_n), tot(-1) { rz(hd, n, -1), rz(d, n, 0), rz(deg, n, 0), e.clear(); }
	void add_edge(int u, int v, ll w) { e.eb((edge) { v, hd[u], w }), hd[u] = ++tot; }
	void add_flow(int u, int v, ll w) { add_edge(u, v, w), add_edge(v, u, 0); }
	void add_lim(int u, int v, ll l, ll r) { add_flow(u, v, r - l), deg[u] -= l, deg[v] += l; }
	bool bfs() {
		fill(d.begin(), d.end(), 0);
		queue<int> q; q.push(s), d[s] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = hd[u]; ~i; i = e[i].nxt) {
				int v = e[i].to;
				if (!e[i].w || d[v]) continue;
				d[v] = d[u] + 1, q.push(v);
			}
		}
		return d[t];
	}
	ll dfs(int u, ll in) {
		if (u == t) return in;
		ll out = 0;
		for (int &i = cr[u]; ~i; i = e[i].nxt) {
			int v = e[i].to;
			if (e[i].w && d[v] == d[u] + 1) {
				ll res = dfs(v, min(in, e[i].w));
				in -= res, out += res;
				e[i].w -= res, e[i ^ 1].w += res;
			}
			if (!in) break;
		}
		if (!out) d[u] = 0;
		return out;
	}
	ll dinic() {
		ll sum = 0, mf = 0;
		s = n - 1, t = n; 
		for (int i = 1; i <= n; i++) {
			if (deg[i] > 0) add_flow(s, i, deg[i]), sum += deg[i];
			if (deg[i] < 0) add_flow(i, t, -deg[i]);
		}
		while (bfs()) cr = hd, mf += dfs(s, inf);
		return sum - mf;
	}
};

int n, m;
struct E { int u, v, a, b, c, d; } e[M];

ll gap(int w) {
	Flow G(n + 2);
	for (int i = 1; i <= m; i++) {
		auto [u, v, a, b, c, d] = e[i];
		G.add_lim(u, v, 1ll * a * w + 1ll * b * L, 1ll * c * w + 1ll * d * L);
	}
	return G.dinic();
}

void solve() {
	cin >> n >> m;
	for (int i = 1, u, v, a, b, c, d; i <= m; i++) 
		cin >> u >> v >> a >> b >> c >> d, e[i] = (E) { u, v, a, b, c, d };
	int l = 0, r = L, pl, pr;
	while (r - l >= 5) {
		int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
		if (gap(m1) <= gap(m2)) r = m2;
		else l = m1;
	}
	pi res = mp(inf, L);
	for (int i = l; i <= r; i++) res = min(res, mp(gap(i), i));
	if (res.fi) return cout << 0 << '\n', void();
	pl = pr = res.se, l = pl + 1, r = L;
	while (l <= r) {
		int md = (l + r) >> 1;
		if (gap(md) == res.fi) l = md + 1, pr = md;
		else r = md - 1;
	}
	l = 0, r = pl - 1;
	while (l <= r) {
		int md = (l + r) >> 1;
		if (gap(md) == res.fi) r = md - 1, pl = md;
		else l = md + 1;
	}
	cout << fixed << setprecision(6) << 1. * (pr - pl) / L << '\n';
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen("1.in", "r", stdin);
		freopen("1.out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}