Cod sursa(job #141663)

Utilizator vlad.maneaVlad Manea vlad.manea Data 23 februarie 2008 15:40:38
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>
#include <values.h>

#define nmax 256

int N, ans;

int viz[nmax], cat[nmax];

int cap[nmax][nmax], nod[nmax*nmax];

void read()
{
	int i;

	freopen("harta.in", "r", stdin);
	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		scanf("%d%d", &cap[i+N][N+N+1], &cap[0][i]);
}

int bfs()
{
	int i, j, ic, sc, flux;

	for (viz[0] = -1, cat[0] = MAXINT, i = 1; i <= N+N+1; ++i)
		viz[i] = cat[i] = MAXINT;

	nod[ic = sc = 0] = 0;

	while (ic <= sc)
	{
		i = nod[ic++];
		for (j = 0; j <= N+N+1; j++)
			if (cap[i][j] > 0 && viz[j] == MAXINT)
			{
				nod[++sc] = j;
				viz[j] = i;
				cat[j] = cap[i][j] < cat[i]? cap[i][j]: cat[i];
			}
	}

	if (viz[N+N+1] == MAXINT)
		return 1;

	for (flux = cat[N+N+1], j = N+N+1; viz[j] != -1; j = viz[j])
	{
		i = viz[j];
		cap[i][j] -= flux;
		cap[j][i] += flux;
	}

	return 0;
}

void solve()
{
	int i, j;

	// creez reteaua de transport
	for (i = 1; i <= N; ++i)
		for (j = N+1; j <= N+N; ++j)
			if (j-N != i)
				cap[i][j] = 1;

	while (!bfs());

	for (i = 1; i <= N; ++i)
		for (j = N+1; j <= N+N; ++j)
			if (cap[j][i] == 1)
				ans++;
}

void write()
{
	int i, j;

	freopen("harta.out", "w", stdout);

	printf("%d\n", ans);

	for (i = 1; i <= N; ++i)
		for (j = N+1; j <= N+N; ++j)
			if (cap[j][i] == 1)
				printf("%d %d\n", j-N, i);
}

int main()
{
	read();
	solve();
	write();

	return 0;
}