Cod sursa(job #2384260)

Utilizator petrea1551Petrea Calin petrea1551 Data 20 martie 2019 15:55:03
Problema Flux maxim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 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;
	q.push(1);
	while (!q.empty())
	{
		int nod = q.front();
		q.pop();
		for (int i = 0; i < v[nod].size(); i++)
			if (c[nod][v[nod][i]] != f[nod][v[nod][i]] || !viz[v[nod][i]])
			{
				viz[v[nod][i]] = 1;
				q.push(v[nod][i]);
				p[v[nod][i]] = nod;
				if (v[nod][i] == 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;
		c[x][y] += z;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int flow = 0;
	while (BFS())
	{
		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;
}