Cod sursa(job #1435761)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 14 mai 2015 13:49:25
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int n, m, F[210][210], C[210][210], S, D, pred[210], maxflow;
vector <int> G[210];
queue <int> Q;

bool Accesibil()
{
	int i, x;
	vector <int>::iterator it;
	for(i = 1; i <= D; ++i)
		pred[i] = -1;
	pred[S] = 0;
	Q.push(S);
	while(!Q.empty())
	{
		x = Q.front();
		Q.pop();
		for(it = G[x].begin(); it != G[x].end(); ++it)
		{
			if(pred[*it] == -1 && F[x][*it] < C[x][*it])
			{
				pred[*it] = x;
				Q.push(*it);
			}
		}
	}
	if(pred[D] == -1)
		return false;
	return true;
}

void MaxFlow()
{
	int x, val;
	vector <int>::iterator it;
	while(Accesibil())
	{
		for(it = G[D].begin(); it != G[D].end(); ++it)
		{
			if(F[*it][D] >= C[*it][D])
				continue;
			x = *it;
			val = C[x][D] - F[x][D];
			while(pred[x])
			{
				val = min(val, C[pred[x]][x] - F[pred[x]][x]);
				x = pred[x];
			}
			maxflow += val;
			x = *it;
			F[x][D] += val;
			F[D][x] -= val;
			while(pred[x])
			{
				F[pred[x]][x] += val;
				F[x][pred[x]] -= val;
				x = pred[x];
			}
		}
	}
}

int main()
{
	int i, j, nrin, nrout;
	ifstream fin("harta.in");
	fin >> n;
	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= n; ++j)
		{
			if(i == j)
				continue;
			G[i].push_back(j + n);
			G[j + n].push_back(i);
			C[i][j + n] = 1;
		}
	}
	S = 2 * n + 1;
	D = 2 * n + 2;
	for(i = 1; i <= n; ++i)
	{
		fin >> nrout >> nrin;
		
		G[S].push_back(i);
		G[i].push_back(S);
		C[S][i] = nrout;
		
		G[i + n].push_back(D);
		G[D].push_back(i + n);
		C[i + n][D] = nrin;
	}
	fin.close();
	
	MaxFlow();
	
	ofstream fout("harta.out");
	m = maxflow;
	fout << m << "\n";
	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= n; ++j)
		{
			if(i == j)
				continue;
			if(F[i][j + n] == 1)
				fout << i << ' ' << j << "\n";
		}
	}
	fout.close();
	return 0;
}