Cod sursa(job #1443583)

Utilizator radudorosRadu Doros radudoros Data 28 mai 2015 11:31:54
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int n, s, nod, in[101], out[101], m[101][101], v[101];
int C[205][205],F[205][205] ;
vector<int> G[205];
int maxflow = 0;
int tata[205];

int bfs(int s)
{
	queue<int>q;
	for (int i = 0; i <= n; i++)
	{
		tata[i] = -1;
	}
	tata[s] = 0;
	q.push(s);
	while (!q.empty())
	{
		int x = q.front();
		for (int i = 0; i < G[x].size(); i++)
		{
			if (tata[G[x][i]] == -1 && F[x][G[x][i]] != C[x][G[x][i]])
			q.push(G[x][i]);
			tata[i] = x;
		}
	}
	if (tata[n] == -1)
		return 0;
	return 1;
}

void Maxflow()
{
	int D = n;
	while (bfs(0))
	{
		for (vector<int>::iterator it = G[D].begin(); it != G[D].end(); it++)
		{
			if (F[*it][D] == C[*it][D])
				continue;
			int val = C[*it][D] - F[*it][D];
			int crt = *it;
			while (tata[crt])
			{
				val = min(val, C[tata[crt]][crt] - F[tata[crt]][crt]);
				crt= tata[crt];
			}
			maxflow += val;
			F[*it][D] += val;
			F[D][*it] -= val;
			crt = *it;
			while (tata[crt])
			{
				F[tata[crt]][crt] += val;
				F[crt][tata[crt]] -= val;
				crt = tata[crt];
			}
		}
	}
}


int main()
{
	ifstream fin("harta.in");
	ofstream fout("harta.out");
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		int innr, outnr;
		fin >> innr >> outnr;
		G[0].push_back(i);
		G[i].push_back(0);
		C[0][i] = innr;
		G[i + n].push_back(2 * n + 1);
		G[2 * n + 1].push_back(i + n);
		C[i + n][2 * n + 1] = outnr;
		for (int j = 1; j <= n; j++)
		{
			if (i != j)
			{
				G[i].push_back(n + j);
				G[j + n].push_back(i);
				C[i][j + n] = 1;
			}
		}
	}
	int nr = n;
	n = 2 * n + 1;

	Maxflow();

	fout << maxflow<<'\n';
	for (int i = 1; i <= nr; i++)
	{
		for (int j = 1; j <= nr; j++)
		{
			if (i != j&&F[i][j + n] == 1)
				fout << i << ' ' << j << '\n';

		}
	}

}