Cod sursa(job #319781)

Utilizator CezarMocanCezar Mocan CezarMocan Data 2 iunie 2009 09:11:42
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 110

using namespace std;

int c[2 * maxn][2 * maxn], flux[2 * maxn], up[2 * maxn];
int i, j, n, sink, dest, ok, futot, a, b;
vector <pair<int, int> > sol;
vector <pair<int, int> >::iterator it;

void init() {
	ok = 0;
	memset(flux, 0, sizeof(flux));
	memset(up, -1, sizeof(up));
	flux[sink] = 2000000000;
}

inline int min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

void bf() {
	int p, u, cd[2 * maxn];
	int i, nod, ant;
	p = u = 1;
	cd[1] = sink;
	while (p <= u) {
		nod = cd[p];
		for (i = 1; i <= 2 * n + 2; i++)
			if (c[nod][i] && flux[i] == 0) {
				u++;
				cd[u] = i;
				flux[i] = min(c[nod][i], flux[nod]);
				up[i] = nod;
				if (i == dest) {
					p = u + 1;
					break;
				}
			}
		p++;
	}

/*	for (i = 1; i <= u; i++)
		fprintf(stderr, "%d ", cd[i]);
	fprintf(stderr, "\n");*/

//	fprintf(stderr, "%d\n", flux[dest]);
	ok = flux[dest];
	if (ok) {
		nod = dest;
		while (nod != sink) {
			ant = up[nod];	
			c[ant][nod] -= flux[dest];
			c[nod][ant] += flux[dest];
			nod = ant;
		}
	}

}

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

	scanf("%d", &n);

	//fac sursa 2*N+1 si destinatia 2*N+2
	sink = 2 * n + 1;
	dest = 2 * n + 2;

	for (i = 1; i <= n; i++) {
		scanf("%d%d", &a, &b);
		c[sink][i] = c[i][sink] = b;
		c[i + n][dest] = c[dest][i + n] = a;
	}

	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i != j)
				c[i][j + n] = 1;
	
	ok = 1;
	while (ok) {
		init();
		bf();
//		fprintf(stderr, "%d\n", flux[dest]);
	}

	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i != j && c[i][j + n] == 0)
				sol.push_back(make_pair(j, i));

	printf("%d\n", sol.size());
	for (it = sol.begin(); it != sol.end(); ++it)
		printf("%d %d\n", it->first, it->second);

	return 0;
}