Cod sursa(job #670170)

Utilizator Catah15Catalin Haidau Catah15 Data 28 ianuarie 2012 16:20:28
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

#define maxN 210
#define PB push_back
#define inf (1 << 30)

bool cont[maxN];
int cp[maxN][maxN], fl[maxN][maxN], tata[maxN];
int sol, N;
queue <int> Q;
vector <int> lista[maxN];

int poti_pompa ()
{
	Q.push (0);
	
	memset (cont, 0, sizeof (cont));
	
	while (! Q.empty ())
	{
		int nod = Q.front();
		Q.pop();
		
		for (unsigned int i = 0; i < lista[nod].size(); ++ i)
		{
			int nod2 = lista[nod][i];
			
			if (cp[nod][nod2] - fl[nod][nod2] == 0) continue;
			if (cont[nod2]) continue;
			
			Q.push (nod2);
			tata[nod2] = nod;
			
			cont[nod2] = true;
		}
	}
	
	if ( ! cont[N * 2 + 1] ) return 0;
	
	int nod = 2 * N + 1;
	int minim = inf;
	
	while (nod)
	{
		minim = min (minim, cp[tata[nod]][nod] - fl[tata[nod]][nod]);
		nod = tata[nod];
	}
	
	nod = 2 * N + 1;
	
	while (nod)
	{
		fl[tata[nod]][nod] += minim;
		fl[nod][tata[nod]] -= minim;
		nod = tata[nod];
	}
	
	sol += minim;
	
	return 1;
	
}

int main()
{
	freopen ("harta.in", "r", stdin);
	freopen ("harta.out", "w", stdout);
	
	scanf ("%d", &N);
	
	for (int i = 1; i <= N; ++ i)
	{
		int in, out;
		
		scanf ("%d %d", &in, &out);
		
		cp[0][i] = in;
		cp[i + N][2 * N + 1] = out;
		
		lista[0].PB (i);
		lista[i].PB (0);
		
		lista[i + N].PB (2 * N + 1);
		lista[2 * N + 1].PB (i + N);
	}
	
	for (int i = 1; i <= N; ++ i)
		for (int j = N + 1; j <= 2 * N; ++ j)
		{
			if (j - N == i) continue;
			
			cp[i][j] = 1;
			
			lista[i].PB (j);
			lista[j].PB (i);
		}
	
	while (poti_pompa());
	
	printf ("%d \n", sol);
	
	for (int i = 1; i <= N; ++ i)
		for (int j = N + 1; j <= 2 * N; ++ j) if (fl[i][j] == 1) printf ("%d %d\n", i, j - N);
	
	return 0;
}