Cod sursa(job #2423760)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 21 mai 2019 21:57:57
Problema Flux maxim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int INF = 0x3f3f3f3f;

int i, n, m, x, y, z, cap[N][N], flow[N][N], exc[N], h[N];

void push(int x, int y) {
	int addFlow = min(exc[x], cap[x][y] - flow[x][y]);
//	cerr << x << ' ' << y << ' ' << addFlow << '\n';
	flow[x][y] += addFlow;
	flow[y][x] -= addFlow;
	exc[x] -= addFlow;
	exc[y] += addFlow;
}

void relabel(int x) {
	int d = INF;
	for (int i = 1; i <= n; ++i) if (cap[x][i] - flow[x][i] > 0) d = min(d, h[i]);
	if (d < INF) h[x] = d + 1;
}

vector<int> getMHV() {
	vector<int> ans;
	for (int i = 2; i < n; ++i) {
		if (!exc[i]) continue;
		if (ans.size() && h[i] > h[ans[0]]) ans.clear();
		if (!ans.size() || h[i] == h[ans[0]]) ans.push_back(i);
	}
 	return ans;
}

int maxFlow() {
	h[1] = n;
	exc[1] = INF;
	for (int i = 2; i <= n; ++i) push(1, i);
	for (vector<int> v = getMHV(); v.size(); v = getMHV()) {
		for (int x : v) {
			bool pushed = false;
			for (int i = 1; i <= n && exc[x]; ++i) {
				if (cap[x][i] - flow[x][i] > 0 && h[x] == h[i] + 1) {
					push(x, i);
					pushed = true;
				}
			}
			if (!pushed) {
				relabel(x);
				break;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += flow[i][n];
	}
	return ans;
}

int main() {
	freopen("maxflow.in", "r", stdin);
	freopen("maxflow.out", "w", stdout);
	for(scanf("%d %d", &n, &m); m; --m) {
		scanf("%d %d %d", &x, &y, &z);
		cap[x][y] += z;
	}
	printf("%d\n", maxFlow());
	return 0;
}