Cod sursa(job #324269)

Utilizator FlorianFlorian Marcu Florian Data 15 iunie 2009 12:13:50
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define MAX_N 256
#define Inf 0x3f3f3f3f
int N, S, D;
queue<int> Q;
int c[MAX_N][MAX_N];
bool viz[MAX_N];
int tata[MAX_N];
inline bool BFS()
{
	int x,y;
	int i;
	for(;!Q.empty();Q.pop());
	Q.push(S);
	memset(viz,0,sizeof(viz));
	viz[S] = 1;
	for(;!Q.empty();Q.pop())
	{
		x = Q.front();
		for(y=1;y<=2*N+2;++y)
			if(!viz[y] && c[x][y])
			{
				tata[y] = x;
				Q.push(y);
				viz[y] = 1;
			}
	}
	if(viz[D])
	{
		int flx = Inf;
		for(i = D; i!=S; i = tata[i])
			flx = min(flx, c[tata[i]][i]);
		for(i = D; i!=S; i = tata[i])
		{
			c[tata[i]][i] -= flx;
			c[i][tata[i]] += flx;
		}
		return 1;
	}
	return 0;
}
int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d",&N);
	int i,j,x,y;
	int sol = 0;
	S = 2*N + 1; D = 2*N + 2;
	for(i=1;i<=N;++i)
	{
		scanf("%d%d",&x,&y);
		sol += x;
		c[S][i] = c[i][S] = x;
		c[i+N][D] = c[D][i+N] = y;
	}
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j)
			if(i!=j) c[i][j+N] = 1;
	for(;BFS(););
	printf("%d\n",sol);
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j)
			if(i!=j && !c[i][j+N])
				printf("%d %d\n",i,j);
	return 0;
}