Cod sursa(job #2387942)

Utilizator petrea1551Petrea Calin petrea1551 Data 25 martie 2019 14:44:53
Problema Flux maxim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
 
int n, m, c[1001][1001], f[1001][1001], viz[1001];
queue<int> q;
vector<int> v[1001];
 
bool BFS()
{
	memset(viz, -1, sizeof(viz));
	viz[1] = 0;
	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] != -1)
					continue;
				viz[V] = 1;
				q.push(V);
				viz[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)
		for (int i = 0; i < v[n].size(); i++)
		{
			int nod = v[n][i];
			if (viz[nod] == -1) continue;
			viz[n] = nod;
			int fmin = 100000000;
			for (int nod = n; nod != 1; nod = viz[nod])
				fmin = min(c[viz[nod]][nod] - f[viz[nod]][nod], fmin);
			for (int nod = n; nod != 1; nod = viz[nod])
			{
				f[viz[nod]][nod] += fmin;
				f[nod][viz[nod]] -= fmin;
			}
			flow += fmin;
		}
	cout << flow;
	return 0;
}