Cod sursa(job #2387927)

Utilizator petrea1551Petrea Calin petrea1551 Data 25 martie 2019 14:32:11
Problema Flux maxim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
 
int n, m, c[1001][1001], f[1001][1001], p[1001];
queue<int> q;
vector<int> v[1001];
bool viz[1001];
 
bool BFS()
{
	memset(viz, 0, sizeof(viz));
	viz[1] = 1;
	while (!q.empty()) q.pop();
	q.push(1);
	while (!q.empty())
	{
		int nod = q.front();
		q.pop();
		for (int i = 0; i < v[nod].size(); i++)
			{
				int V = v[nod][i];
				if (c[nod][V] == f[nod][V] || viz[V])
					continue;
				viz[V] = 1;
				q.push(V);
				p[V] = nod;
				if (V == n)
					return 1;
			}
	}
	return 0;
}
 
int main()
{
	ifstream cin("maxflow.in");
	ofstream cout("maxflow.out");
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		c[x][y] += z;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int flow = 0;
	while (BFS() == 1)
	{
		int fmin = 100000000;
		for (int nod = n; nod != 1; nod = p[nod])
			fmin = min(c[p[nod]][nod] - f[p[nod]][nod], fmin);
		for (int nod = n; nod != 1; nod = p[nod])
		{
			f[p[nod]][nod] += fmin;
			f[nod][p[nod]] -= fmin;
		}
		flow += fmin;
	}
	cout << flow;
	return 0;
}