Cod sursa(job #161408)

Utilizator plastikDan George Filimon plastik Data 17 martie 2008 23:14:30
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <climits>
#include <queue>
#define NMAX 256

using namespace std;

int Cap[NMAX][NMAX], n;

int From[NMAX], ord;
bool Used[NMAX];
queue<int> Q;

int breadthFirst(int src, int snk) {
	int i;
	for (i = 0; i <= snk; ++ i) {
		From[i] = -1;
		Used[i] = false;
	}
	for (; Q.empty() == false; Q.pop())
		;

	Used[src] = true;
	int cur;
	bool stop = false;
	for (Q.push(src); Q.empty() == false && stop == false; Q.pop()) {
		cur = Q.front();
		for (i = 0; i <= snk; ++ i)
			if (Cap[cur][i] > 0 && Used[i] == false) {
				Used[i] = true;
				From[i] = cur;
				Q.push(i);
				if (i == snk) {
					stop = true;
					break;
				}
			}
	}

	int pathCap = INT_MAX;
	for (cur = snk; From[cur] != -1; cur = From[cur]) {
		//printf("%d ", cur);
		pathCap = min(pathCap, Cap[From[cur]][cur]);
		//printf("%d\n", pathCap);
	}
	
	if (pathCap == INT_MAX)
		return 0;

	//printf("%d\n", pathCap);
	for (cur = snk; From[cur] != -1; cur = From[cur]) {
		Cap[From[cur]][cur] -= pathCap;
		Cap[cur][From[cur]] += pathCap;
	}

	return pathCap;
}

void printCap() {
	int i, j, snk = 2 * n + 1;
	printf("%d\n", ord);
	for (i = 0; i <= snk; ++ i) {
		for (j = 0; j <= snk; ++ j)
			printf("%d ", Cap[i][j]);
		printf("\n");
	}
}

int main() {

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

	scanf("%d", &n);
	int i, snk = 2 * n + 1;
	for (i = 1; i <= n; ++ i)
		scanf("%d %d", &Cap[0][i], &Cap[i + n][snk]);

	int j;
	for (i = 1; i <= n; ++ i)
		for (j = 1; j <= n; ++ j)
			if (i != j)
				Cap[i][j + n] = 1;

	int pathCap, ans = 0;
	for (ord = 1, pathCap = breadthFirst(0, snk); pathCap != 0; pathCap = breadthFirst(0, snk), ++ ord) {
		ans += pathCap;
		//printCap();
	}

	printf("%d\n", ans);
	for (i = 1; i <= n; ++ i)
		for (j = n + 1; j < snk; ++ j)
			if (Cap[j][i] > 0)
				printf("%d %d\n", i, j - n);

	return 0;
}