Cod sursa(job #180032)

Utilizator scvalexAlexandru Scvortov scvalex Data 16 aprilie 2008 16:26:38
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>

using namespace std;

int N,
    in[100],
    out[100];
int K,
    U[20000],
    V[20000];

bool did[100][100];

int main(int argc, char *argv[]) 
{
	FILE *fi = fopen("harta.in", "r");
	fscanf(fi, "%d", &N);
	int tot(0);
	for (int i(0); i < N; ++i) {
		fscanf(fi, "%d %d", out+i, in+i);
		tot += out[i];
	}
	fclose(fi);

	FILE *fo = fopen("harta.out", "w");
	fprintf(fo, "%d\n", tot);
	for (int i(0); i < N; ++i)
		for (int j(0); (j < N) && (out[i] > 0); ++j)
			if ((in[j] > 0) && !did[i][j] && (i != j)) {
				U[K] = i;
				V[K++] = j;
				--out[i];
				--in[j];
				did[i][j] = did[j][i] = true;
			}

	int j;
	for (int i(0); i < N; ++i)
		if (out[i] > 0) {
			for (j = 0; (j < N) && (in[j] == 0); ++j)
				;
			for (int k(0); k < K; ++k)
				if (!did[U[k]][j] && !did[i][V[k]] && (U[k] != j) && (V[k] != i)) {
					did[U[k]][j] = did[i][V[k]] = true;
					did[U[k]][V[k]] = false;
					V[k] = j;
					U[K] = i;
					V[K++] = V[k];
					break;
				}
			--in[j];
			--out[i];
			--i;
		}

	for (int i(0); i < K; ++i)
		fprintf(fo, "%d %d\n", U[i]+1, V[i]+1);
	fclose(fo);

	return 0;
}