Cod sursa(job #585241)

Utilizator dcm9000Dinu Cristian Mircea - UPB dcm9000 Data 28 aprilie 2011 18:08:12
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

#define INF 32000

int N;
int GREX[100];
int GRIN[100];

int SRC;
int DEST;

short MATAD[202][202];
short FLUX[202][202];

typedef struct _QElem {
	int node, level;
	short cap;
	struct _QElem* parent;
} QElem;

static void initMatad() {
	memset(MATAD, 0, 202*202*sizeof(short));

	for (int i=0; i<2*N+2; i++) {
		for (int j=0; j<2*N+2; j++) {
			if ((i == SRC) && (j < N)) {
				MATAD[i][j] = GREX[j];
			} else if ((i >= N) && (i < 2*N) && (j == DEST)) {
				MATAD[i][j] = GRIN[i-N];
			} else if ((i < N) && (j >= N) && (j < 2*N) && (i != j-N)) {
				MATAD[i][j] = 1;
			}
		}
	}
}

static void initFlux() {
	memset(FLUX, 0, 202*202*sizeof(short));
}

static void push(int a, int b, short amount) {
	FLUX[a][b] += amount;
	FLUX[b][a] -= amount;
	MATAD[a][b] -= amount;
	MATAD[b][a] += amount;
}

static void fluxMax() {
	static QElem queue[202];
	static int visited[202];
	int start;
	int end;
	QElem* dest;

	while (1) {
		start = 0;
		end = 0;
		dest = NULL;
		memset(visited, 0, sizeof(int)*202);
		queue[end].node = SRC;
		queue[end].level = 0;
		queue[end].cap = INF;
		queue[end].parent = NULL;
		end++;

		while (start < end) {
			int nodC = queue[start].node;

			for (int i=0; i<2*N+2; i++) {
				if ((MATAD[nodC][i] > 0) && !visited[i]) {
					visited[i] = 1;
					queue[end].node = i;
					if (i == DEST) dest = queue+end;
					queue[end].parent = queue+start;
					queue[end].level = queue[start].level+1;
					queue[end].cap = min(queue[start].cap, MATAD[nodC][i]);
					end++;
				}
			}
			start++;
		}

		if (!dest) return;

		short destCap = dest->cap;
		while (dest->parent != NULL) {
			push(dest->parent->node, dest->node, destCap);
			dest = dest->parent;
		}
	}
}

int main(int argc, char** argv) {
	ifstream fisIn("harta.in");
	ofstream fisOut("harta.out");

	fisIn >> N;
	for (int i=0; i<N; i++) {
		fisIn >> GREX[i] >> GRIN[i];
	}

	SRC = 2*N;
	DEST = 2*N+1;

	initMatad();
	initFlux();
	fluxMax();

	int count = 0;
	for (int i=0; i<2*N; i++) {
		for (int j=0; j<2*N; j++) {
			if (FLUX[i][j] > 0) count++;
		}
	}
	fisOut << count << "\n";
	for (int i=0; i<2*N; i++) {
		for (int j=0; j<2*N; j++) {
			if (FLUX[i][j] > 0)
				fisOut << (i+1) << " " << (j-N+1) << "\n";
		}
	}
	fisOut.close();

	return 0;
}