Cod sursa(job #331208)

Utilizator cotofanaCotofana Cristian cotofana Data 13 iulie 2009 00:34:54
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <cstring>
#include <queue>
#define dim 256

using namespace std;

int n, c[dim][dim], ct=0, p[dim], f=0;
queue<int> q;

int bfs() {
	int nod, i, viz[dim];
	
	while (!q.empty()) q.pop();
	memset(viz, 0, sizeof(viz));
	q.push(0);
	viz[0]=1;
	
	while (!q.empty()) {
		nod=q.front();
		q.pop();
		if (nod==2*n+1) continue;
		
		for (i=0; i<=2*n+1; ++i)
			if (i!=nod && c[nod][i] && !viz[i]) {
				viz[i]=1;
				p[i]=nod;
				q.push(i);
			}
	}
	return viz[2*n+1];
}

int main() {
	int i, j, in, out, fm;
	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);
	
	scanf("%d\n", &n);
	for (i=1; i<=n; ++i) {
		scanf("%d %d\n", &in, &out);
		ct+=in;
		c[0][i]=in;
		c[i+n][2*n+1]=out;
	}
	for (i=1; i<=n; ++i)
		for (j=n+1; j<=2*n; ++j) 
			if (i!=j-n) c[i][j]=1;
	
	for (; bfs(); )
		for (i=n+1; i<=2*n; ++i)
			if (c[i][2*n+1]) {
				p[2*n+1]=i;
				fm=1<<30;
				
				for (j=2*n+1; j; j=p[j])
					if (c[p[j]][j]<fm) fm=c[p[j]][j];
				if (!fm) continue;
				
				for (j=2*n+1; j; j=p[j]) {
					c[p[j]][j]-=fm;
					c[j][p[j]]+=fm;
				}
				f+=fm;
			}
	
	printf("%d\n", ct);
	for (i=1; i<=n; ++i)
		for (j=n+1; j<=2*n; ++j)
			if (!c[i][j] && i!=j-n) printf("%d %d\n", i, j-n);
	
	return 0;
}