Cod sursa(job #567111)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 29 martie 2011 18:50:24
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define maxn 210
#define inf 0x3f3f3f3f
#define VIT vector <int> :: iterator

using namespace std;

int dad[maxn], f[maxn][maxn], matCap[maxn][maxn];
vector <int> G[maxn];
vector <pair <int, int> > sol;
int S, D, N;

inline bool BF ()
{
	for (int i = S; i <= D; i++)
		dad[i] = 0;

	queue <int> Q;	
	Q.push (S);
	int nod;	

	while (!Q.empty ()) {
		
		nod = Q.front (); 
		Q.pop ();
		
		if (nod == D) return 1;

		for (VIT it = G[nod].begin (); it != G[nod].end (); it++) 
			if (dad[*it] == 0 && matCap[nod][*it] > f[nod][*it]) {
				dad[*it] = nod;
				Q.push (*it);
			}
	}
	return 0;
}
int main ()
{

	freopen ("harta.in", "r", stdin);
	freopen ("harta.out", "w", stdout);


	scanf ("%d\n", &N);
	
	int nod, x, y;

	S = 0; D = (N << 1) + 2;
	for (int i = 1; i <= N; i++) {
		scanf ("%d %d\n", &x, &y);
		
		G[S].push_back (i);

		G[i + N].push_back (D);
		G[D].push_back (i + N);

		matCap[S][i] = matCap[i][S] = x;
		matCap[i + N][D] = matCap[D][i + N] = y;
	}

	for (int i = 1; i <= N; i++)
		for (int j = N + 1; j <= (N << 1) + 1; j++)
			if (i != j - N) {
				matCap[i][j] = 1;
				G[i].push_back (j);
				G[j].push_back (i);
			}
	

	int tmpflow;

	for (; BF (); ) 
	{
		for (VIT it = G[D].begin (); it != G[D].end (); it++) {
			nod = *it;
			
			dad[D] = nod;
			tmpflow = inf;
			
			for (int i = D; i != S; i = dad[i]) 
				tmpflow = min (tmpflow, matCap[dad[i]][i] - f[dad[i]][i]);
			if (tmpflow == 0)
				continue;
			
			for (int i = D; i != S; i = dad[i]) {
				f[dad[i]][i] += tmpflow;
				f[i][dad[i]] -= tmpflow;
			}
			
		}
	}
	
	for (int i = 1; i <= N; i++) 
		for (int j = N + 1; j <= (N << 1) + 1; j++)
			if (i != j - N && f[i][j] == 1) 
				sol.push_back (make_pair (i, j - N));

	printf ("%d\n", sol.size ());
	
	for (int i = 0; i < sol.size (); i++) 
		printf ("%d %d\n", sol[i].first, sol[i].second);

	return 0;
}