Cod sursa(job #479327)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 23 august 2010 18:06:11
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#include <string.h>

#include <vector>
#include <queue>

using namespace std;

int n, up[205];
int c[205][205], f[205][205];
vector <int> v[205];

inline int calc (int a, int b) {return c[a][b] - f[a][b];}
inline int minim (int a, int b) {return a < b ? a : b;}

int bfs ()
{
	memset (up, -1, sizeof (up));
	up[0] = -2;
	
	int nod;
	queue <int> q;
	q.push (0);
	
	while (!q.empty ())
	{
		nod = q.front ();
		q.pop ();
		
		for (vector <int> :: iterator it = v[nod].begin (); it != v[nod].end (); it ++)
			if (up[*it] == -1 && c[nod][*it] > f[nod][*it])
			{
				up[*it] = nod;
				if (*it == 2 * n + 1)
					return 1;
				
				q.push (*it);
			}
	}
	return 0;
}

void flux ()
{
	int nod, min;
	
	while (bfs ())
	{
		nod = 2 * n + 1;
		
		min = calc (up[nod], nod);
		while (up[nod] != -2)
		{
			min = minim (min, calc (up[nod], nod));
			nod = up[nod];
		}
		
		nod = 2 * n + 1;
		while (up[nod] != -2)
		{
			f[up[nod]][nod] += min;
			f[nod][up[nod]] -= min;
			nod = up[nod];
		}
	}
}

int main ()
{
	freopen ("harta.in", "r", stdin);
	freopen ("harta.out", "w", stdout);
	
	scanf ("%d", &n);
	
	int i, j, s = 0, cap;
	for (i = 1; i <= n; i ++)
	{
		scanf ("%d", &cap);
		s += cap;
		c[0][i] = cap;
		v[0].push_back (i);
		v[i].push_back (0);
		
		scanf ("%d", &cap);
		c[n + i][2 * n + 1] = cap;
		v[n + i].push_back (2 * n + 1);
		v[2 * n + 1].push_back (n + i);
	}
	
	for (i = 1; i <= n; i ++)
		for (j = n + 1; j <= n + n; j ++)
			if (j - i != n)
			{
				c[i][j] = 1;
				v[i].push_back (j);
				v[j].push_back (i);
			}
	
	flux ();
	
	printf ("%d\n", s);
	for (i = 1; i <= n; i ++)
		for (j = 1; j <= n; j ++)
			if (f[i][j + n] > 0)
				printf ("%d %d\n", i, j);
	return 0;
}