Cod sursa(job #141166)

Utilizator SycronVene Tian Sycron Data 22 februarie 2008 20:09:38
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 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;   
}