Cod sursa(job #319793)

Utilizator savimSerban Andrei Stan savim Data 2 iunie 2009 10:30:52
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 512
#define inf 2147000000

int n, i, j, fin, improve, flow, sol;
int C[MAX_N][MAX_N];
int Q[MAX_N], tata[MAX_N], flux[MAX_N];

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

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		int p = 0, q = 0;
		scanf("%d %d", &p, &q);
		sol += p + q;

		C[2 * i][2 * i + 1] = p;
		C[2 * i + 2 * n][2 * i + 2 * n + 1] = q;
	}

	fin = 4 * n + 2;
	for (i = 1; i <= n; i++) {
		C[1][2 * i] = C[2 * i][2 * i + 1];
		C[2 * i + 2 * n + 1][fin] = C[2 * i + 2 * n][2 * i + 2 * n + 1];
	}

	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i != j)
				C[2 * i + 1][2 * n + 2 * j] = 1;
}

void bfs() {
	int st = 0, dr = 1;

	flux[1] = inf;
	while (st < dr) {
		st++;

		for (i = 1; i <= fin; i++)
			if (flux[i] == 0 && C[Q[st]][i]) {
				int x = min(flux[Q[st]], C[Q[st]][i]);
				
				flux[i] = x;

				Q[++dr] = i;
				tata[i] = Q[st];
			}
	}

	improve =  flux[fin];

	if (!improve) return;
	else {
		i = fin;

		while (i != 1) {
			C[tata[i]][i] -= flux[fin];
			C[i][tata[i]] += flux[fin];

			i = tata[i];
		}
	}
}

void write() {
    printf("%d\n", sol / 2);

	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (!C[2 * i + 1][2 * n + 2 * j] && C[2 * n + 2 * j][2 * i + 1])
				printf("%d %d\n", i, j);
}

int main() {

    cit();

/*    improve = 1;
	while (improve) {
		Q[1] = 1;
		bfs();
		flow += improve;

		memset(tata, 0, sizeof(tata));
		memset(flux, 0, sizeof(flux));
	} */

	write();

	return 0;
}