Cod sursa(job #130746)

Utilizator DastasIonescu Vlad Dastas Data 1 februarie 2008 19:47:06
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>

const int maxn = 204;

FILE *in = fopen("harta.in","r"), *out = fopen("harta.out","w");

int n;
int a[maxn][maxn], f[maxn][maxn], gin[maxn], gout[maxn];

int viz[maxn];
int q[maxn];

int g;

void readinit()
{
    fscanf(in, "%d", &n);

    g = 2*n + 1;
    for ( int i = 1; i <= n; ++i )
    {
        fscanf(in, "%d %d", &gin[i], &gout[i]);
        a[0][i] = gin[i];
        a[n + i][g] = gout[i];
    }

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
            if ( i != j )
                a[i][n + j] = 1;
}

int h;
int bf()
{
    for ( int i = 0; i <= g; ++i )
        viz[i] = -1;

    int p = 0, u = 0;

    q[p] = 0;
    viz[p] = 0;

    int x;

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

        for ( int i = 0; i <= g; ++i )
            if ( f[x][i] < a[x][i] && viz[i] == -1 )
            {
                viz[i] = x, q[++u] = i;

                if ( i == g )
                    return 1;
            }
    }

    return 0;
}

void go()
{
    while ( bf() )
    {
        ++h;

        for ( int i = g; i; i = viz[i] )
            ++f[ viz[i] ][i], --f[i][ viz[i] ];
    }
}

int main()
{
    readinit();
    go();

    fprintf(out, "%d\n", h);

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
            if ( f[i][j + n] )
                fprintf(out, "%d %d\n", i, j);

	return 0;
}