// f=0 для всех рёбер
// if нет отрицательных циклов
// 	{ f оптимален }
// else
// 	{ нужно найти циркуляцию минимального веса }

// for k раз
// 	path = FordBellman
// 	f(path) += 1

// ------------------------

// Если f_k оптимален =>
// f_{k+1} оптимален

// w[обратного] = -w[прямого]

// ФФ : k * dfs
// ФФ : k * FB

// FB : O(VE)
// FB с очередью : ~O(V+E)

// k-flow
struct Graph {
	struct Edge {
		int a, b, f, c, w, next;
	};
	vector<Edge> edges;
	vector<int> head;
	Graph(int n) : head(n, -1) { }

	void addEdge(int a, int b, int c, int w) {
		edges.push_back({a, b, 0, c, w, head[a]});
		head[a] = edges.size() - 1;
		edges.push_back({a, b, 0, 0, -w, head[b]});
		head[b] = edges.size() - 1;
	}

	void kflow(int k) {
		// Пусть нет отрицательных циклов
		forn(i, k) {
			queue<int> q;
			vector<int> in_q(n), d(n, INT_MAX);
			auto addQ = [&](int v, int D) {
				if (d[v] > D) {
					d[v] = D;
					if (!in_q[v])
						in_q[v] = q.push(v);
				}
			};
			addQ(s, 0);
			while (q.size()) {
				int v = q.pop();
				for (int i = head[v]; i != -1; i = edges[i].next) {
					auto e = edges[i];
					if (e.f < e.c)
						addQ(e.b, d[v] + e.w);
				}
			}

			Путь

			f(Путь) += 1
			f(Обратным рёбрам пути) -= 1
		}
	}
}

// Mincost c Дейкстрой
d <- FordBellman
for e : w[e] += d[a] - d[b]

// w[e] >= 0 в этот момент
for k
	path, d <- Dijkstra
	for e : w[e] += d[a] - d[b]
	f(path) += 1
	f(рёбрам обратным path) -= 1

Time = FordBellman + k*Dijkstra
TheoryTime = VE + k*(E + VlogV)

Dijkstra = ElogV
Dijkstra = V^2

----------

flow CapacityScaling(c, w) {
	vector c1 = 0
	vector f = 0
	// U = max(c)
	for (k = logU; k >= 0; k--) {
		for (e) if (c[e] & (1 << k)) {
			c1[e] += 1 << k;
			path = FordBellman(start[e], end[e]);
			if (W(path) + w[e] < 0) {
				for j in {path, e}:
					f[j] += 1 << k
					f[reverse(j)] -= 1 << k
			}
		}
	}
}
// Time = logU * E * FordBellman

flow CapacityScaling(c, w) {
	vector c1 = 0
	vector f = 0
	// U = max(c)
	for (k = logU; k >= 0; k--) {
		for (e) if (c[e] & (1 << k)) {
			c1[e] += 1 << k; // w[e] < 0
			if (w[e] >= 0) continue
			// Дейкстра не ходит по ребру "e"
			path, dist = Dijkstra(start[e], end[e]);
			if (W(path) + w[e] < 0)
				for j in {path, e}:
					f[j] += 1 << k
					f[reverse(j)] -= 1 << k
			Применить dist как потенциал
		}
	}
}
// Time = logU * E * Dijkstra