Cod sursa(job #219577)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 7 noiembrie 2008 17:04:36
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int n_max = 210;
int v[n_max][n_max];
int vaz[n_max];
int dev = 0, sup, n, sum; // Super nodes
void make_graph() //Initializing vertices of capaciy 1
{
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= n; ++ j)
			if (i!=j)
			{
				v[i][n+j] = 1;
				v[n+j][i] = 0;
			}
}
int bf() // Searches and finds a path in the flux network
{
	queue < int > q;
	int x;

	q.push(dev); // Initializing the main thing
	memset(vaz,0xff,sizeof(vaz)); // Setting everything to -1
	while (!q.empty())
	{
		x = q.front();
		if (x == sup)
			break;
		for (int i = 0; i <= sup; ++ i)
			if (vaz[i]== -1 && v[x][i] > 0)
			{
				vaz[i] = x;
				q.push(i);
			}
		q.pop();
	}
	if (x != sup)
		return 0;
	// Creating the flux
	while (x != dev)
	{
		--v[vaz[x]][x]; //Erasing only 1 cause that's the maximum possible
		++v[x][vaz[x]];
		x = vaz[x];
	}
	return 1;
}

int main()
{
	int a, b;
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d", &n);
	memset(v,0xff,sizeof(v));
	sup = 2*n+1;
	make_graph();
	for (int i = 1; i <= n; ++ i)
	{
		scanf("%d %d", &a, &b);
		v[0][i] = a;
		v[i+n][sup] = b;
		sum +=a;
	}
	int safety = 0;
	while (bf())
		++safety;
//	if (safety!=sum)
//		printf("Error\n");
	printf("%d\n", sum);
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= n; ++ j)
			if (v[i][n+j] == 0)
				printf("%d %d\n", i,j);
	return 0;

}