Cod sursa(job #282090)

Utilizator blasterzMircea Dima blasterz Data 16 martie 2009 20:54:03
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <string>
#define N 256

int cap[N][N];
int n, in[101], out[101];
int t[N];
int source, sink;

void read()
{
	freopen("harta.in","r",stdin);
	scanf("%d\n", &n);
	for(int i=1; i <= n; ++i) scanf("%d %d\n", &out[i], &in[i]);

	source=0;
	sink=2*n+1;

	int i, j;

	for(i=1; i <= n; ++i) cap[source][i]=out[i];

	for(i=n+1; i < sink; ++i) cap[i][sink]=in[i-n];

	for(i=1; i <= n; ++i)
		for(j=n+1; j < sink; ++j) 
			if(i != j-n) cap[i][j]=1;

}

int bfs()
{
	int Q[N], p=0, q=0,u,i;
	bool use[N];
	memset(use, 0, sizeof(use));
	memset(t, -1, sizeof(t));

	use[source]=1;
	Q[0]=source;

	while(p <= q)
	{
		u=Q[p++];

		for(i=source; i <= sink; ++i)
			if(!use[i])
				if(cap[u][i] > 0)
				{
					Q[++q]=i;
					t[i]=u;
					use[i]=1;
				}
	}

	if(t[sink] == -1) return 0;
	return 1;

}


void solve()
{
	int i, j;
	int flow=0;

	while(bfs())
	{

		for(i=n+1; i < sink; ++i)
			if(t[i] && cap[i][sink] > 0)
			{
				int ok=1;

				while(ok)
				{
					if(cap[i][sink] <= 0) {ok=0; continue;}

					for(j=i; j != source; j=t[j])
						if(cap[t[j]][j] <= 0) { ok=0;break;}

					if(ok == 0) continue;
					--cap[i][sink];
					++cap[sink][i];

					for(j=i; j != source; j=t[j])
						--cap[t[j]][j],
						++cap[j][t[j]];
					++flow;	
				}
			}
			
	}

	freopen("harta.out","w",stdout);
	printf("%d\n", flow);
	for(i=1; i <= n; ++i)
		for(j=n+1; j < sink; ++j)
			if(i != j-n)
				if(cap[i][j] == 0) printf("%d %d\n", i, j-n);


}

int main()
{
	read();

	solve();

	return 0;
}