Cod sursa(job #6312)

Utilizator damaDamaschin Mihai dama Data 18 ianuarie 2007 20:16:16
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <string.h>
#define nmax 202
#define infinit 10000

int n, c[nmax][nmax], used[nmax];

int maxflow();
int bfs();

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

	int i, j, a, b;

	scanf("%d", &n);

	for(i = 1; i <= n; ++i)
	{
		scanf("%d%d", &a, &b);
		c[n + i][nmax - 1] = b;
		c[0][i] = a;
	}

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= n; ++j)
		{
			if(i != j)
			{
				c[i][n + j] = 1;
			}
		}
	}

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

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


	return 0;
}

int maxflow()
{
	int result = 0, path_cap;

	while(1)
	{
		path_cap = bfs();
		if(path_cap)
		{
			result += path_cap;
		}
		else
		{
			break;
		}
	}

	return result;
}

int bfs()
{
	int i;
	int coada[nmax], last = 1, from[nmax], first = 1, where, path_cap = infinit, prev;

	memset(used, 0, sizeof(used));
	coada[1] = 0;

	for(i = 0; i < nmax; ++i)
	{
		from[i] = -1;
	}

	while(first <= last)
	{
		for(i = 1; i < nmax; ++i)
		{
			if(c[coada[first]][i] && !used[i])
			{
				from[i] = coada[first];
				coada[++last] = i;
				used[i] = 1;
			}
		}
		if(used[nmax - 1])
		{
			break;
		}
                ++first;
	}

	where = nmax - 1;

	while(from[where] != -1)
	{
		prev = from[where];
		if(path_cap > c[prev][where])
		{
			path_cap = c[prev][where];
		}
		where = prev;
	}

	where = nmax - 1;

	while(from[where] != -1)
	{
		prev = from[where];
		c[prev][where] -= path_cap;
		c[where][prev] += path_cap;
		where = prev;
	}

	if(path_cap == infinit)
	{
		return 0;
	}
	else
	{
		return path_cap;
	}



}