Cod sursa(job #2423808)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 21 mai 2019 22:49:07
Problema Flux maxim Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,avx,avx2,tune=native")
#pragma GCC optimization("unroll-loops")
#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];
vector<int> lda[N];
 
void push(int x, int y) {
	int addFlow = min(exc[x], cap[x][y] - flow[x][y]);
	flow[x][y] += addFlow;
	flow[y][x] -= addFlow;
	exc[x] -= addFlow;
	exc[y] += addFlow;
}
 
void relabel(int x) {
	int d = INF;
	for (int i : lda[x]) 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 : lda[x]) {
				if (!exc[x]) break;
				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);
		lda[x].push_back(y);
		lda[y].push_back(x);
		cap[x][y] += z;
	}
	for (int i = 1; i <= n; ++i) {
		sort(lda[i].begin(), lda[i].end());
		lda[i].erase(unique(lda[i].begin(), lda[i].end()), lda[i].end());
	}
	printf("%d\n", maxFlow());
	return 0;
}