Cod sursa(job #183275)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 21 aprilie 2008 21:38:57
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <string.h>

int n, c[202][202], source, sink, t[202], f[202][202], viz[202];

int min(int x, int y) { return x < y ? x : y; }

int BF()
{
	int i, q[202], p, u;
	memset(t,0,sizeof(t));
	memset(viz,0,sizeof(viz));

	q[1] = source; p = u = 1;
	viz[0] = 1;
	while (p <= u)
	{
		for (i = 1; i <= 2 * n + 1; i++)
			if (c[q[p]][i] - f[q[p]][i] > 0 && !t[i] && !viz[i])
			{
				q[++u] = i;
				t[i] = q[p];
				if (i == sink) return 1;
				viz[i] = 1;
			}
		p++;
	}
	return 0;
}


void flux()
{
	int i, j, ok;
	while (BF())
	{
		for(i = source; i < sink; i++)
        {
            if(t[i]==-1 || c[i][sink] <= 0)continue;
           
            ok = 1;
            for(j = i; j != source && j != -1; j = t[j]) 
				if(c[t[j]][j] == 0) { ok = 0; break;}

            if(!ok) continue;
   
            c[i][sink] -= 1;
            c[sink][i] += 1;

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

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

	int i, j, x, y, s = 0;	

	scanf("%d",&n);
	source = 0;
	sink = 2 * n + 1;

	for (i = 1; i <= n; i++)
	{
		scanf("%d %d", &x, &y);
		c[source][i] = x;
		c[i + n][sink] = y;	
		s += x;
	}
	printf("%d\n",s);	

	for (i = 1; i <= n; i++)
	{
		for (j = n + 1; j <= 2 * n; j++) c[i][j] = 1;
		c[i][i + n] = 0;
	}
	
	flux();
	return 0;
}