Cod sursa(job #708841)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 7 martie 2012 12:20:40
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream fi ("harta.in");
ofstream fo ("harta.out");

const int dim = 105;
int N, M, Cc, T[dim], C[dim][dim], F[dim][dim], Q[dim];
vector <int> V[dim];

void addmuc (int a, int b, int c)
{
	C[a][b] = c;
	V[a].push_back (b);
	V[b].push_back (a);
}

int bf ()
{
	int p = 0, u = 0, ok = 0, i, n, f;
	Q[0] = 0;
	for (i = 0; i <= M; i++)
		T[i] = 0;
	
	while (p <= u)
	{
		n = Q[p];
		for (i = 0; i < V[n].size(); i++)
		{
			f = V[n][i];
			if (T[f] == 0 && C[n][f] > F[n][f])
			{
				if (f == M)
				{
					ok = 1;
					continue;
				}
				
				Q[++u] = f;
				T[f] = n;
			}
		}		
		p++;
	}
}

void cit ()
{
	fi >> N;
	M = N + N + 1;
	for (int i = 1, j, x, y; i <= N; i++)
	{
		fi >> x >> y;
		
		Cc += x;
		addmuc (0, i, x);
		addmuc (N+i, M, y);
		
		for (j = 1; j <= N; j++)
		{
			if (i != j)
			{
				addmuc (i, N+j, 1);
			}
		}
	}
}

void flux ()
{
	int n, f, m, i;
	
	while ( bf () )
	{
		for (i = 0; i < V[M].size(); i++)
		{
			if (T[V[N][i]] == 0)
				continue;
			
			f = M;
			n = V[M][i];
			m = C[n][f] - F[n][f];
			while (n != 0)
			{
				f = n;
				n = T[f];
				m = min (m, C[n][f] - F[n][f]);
			}
			
			f = M;
			n = V[M][i];
			while (f != 0)
			{
				F[n][f] += m;
				F[f][n] -= m;
				
				f = n;
				n = T[f];
			}
		}		
	}
}

void afi ()
{
	int i, j;
	
	fo << Cc << '\n';
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			if (F[i][j+N] == 1)
				fo << i << ' ' << j << '\n';	
}

int main ()
{
	cit ();
	flux ();
	afi ();
	return 0;
}