Cod sursa(job #2749278)

Utilizator StefanSanStanescu Stefan StefanSan Data 6 mai 2021 09:33:26
Problema Flux maxim Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include      <iostream>
#include      <fstream>
#include      <algorithm>
#include      <queue>

using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");

const int MAX = 1e3 + 1;

int graph[MAX][MAX], n, m;

bool bfs(int G[MAX][MAX], int s, int t, int parent[MAX]) {
	bool visited[MAX];
	for (int i = 1; i <= n; i++) visited[i] = 0;
	queue < int > q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (u == n) continue;
		for (int i = 1; i <= n; i++) {
			if (!visited[i] && G[u][i] > 0) {
				q.push(i);
				parent[i] = u;
				visited[i] = true;
			}
		}
	}

	return visited[n];
}

int max_flow(int G[MAX][MAX], int s, int t) {
	int parent[MAX];
	int maxim = 0;

	while (bfs(G, s, t, parent)) {
		int path_flow = 1e9;
		for (int i = t; i != s; i = parent[i]) {
			path_flow = min(path_flow, G[parent[i]][i]);
		}
		for (int i = t; i != s; i = parent[i]) {
			G[parent[i]][i] -= path_flow;
			G[i][parent[i]] += path_flow;
		}
		maxim += path_flow;
	}
	return maxim;
}

int main() {
	ios_base::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> n >> m;

	for (int i = 1; i <= m; i++) {
		int x, y, c;
		in >> x >> y >> c;
		graph[x][y] = c;
	}

	out << max_flow(graph, 1, n);

	return 0;
}