Cod sursa(job #141524)

Utilizator BuniakovskiNeguletu Octavian Buniakovski Data 23 februarie 2008 12:48:02
Problema Taramul Nicaieri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <stdio.h>   
#include <string.h>   
  
  
#define FIN "harta.in"   
#define FOUT "harta.out"   
#define NMAX 210   
#define ABS( a ) ( (a) < 0 ) ? - a : a   
  
  
int gext[NMAX], gint[NMAX], FLOW[NMAX][NMAX], CAP[NMAX][NMAX];   
int SEL[NMAX], Q[NMAX], T[NMAX];   
int N, i, j, sursa, dest, flow = 0;   
FILE * fin, * fout;   
  
void BFS( int start )   
{   
    int p, u, nod;   
    memset( SEL, 0, sizeof(SEL) );   
    memset( T, 0, sizeof(T) );   
    p = 1; u = 1; Q[p] = start; T[start] = - 1; SEL[start] = 1;   
    while ( ( p <= u ) && (!SEL[dest] ) )   
    {   
        nod = Q[p];   
        for ( i = sursa; i <= dest; i++ )   
            if (!SEL[i])   
            if ( CAP[nod][i] - FLOW[nod][i] > 0 )   
            {   
                T[i] = nod; u++; Q[u] = i; SEL[i] = 1;   
            }else   
                if (FLOW[i][nod] > 0 )   
                {   
                    T[i] = - nod; u++; Q[u] = i; SEL[i] = 1;   
                }   
                p++;   
    }   
}   
  
void RELAX( int xp )   
{   
    int  tata;   
    while (T[xp] != -1 )   
    {   
        tata = ABS( T[xp] );   
        if ( T[xp] > 0 ) FLOW[tata][xp]++; else FLOW[xp][tata]--;   
        xp = tata;   
    }   
}   
  
int main()   
{   
    fin = fopen( FIN, "r" );   
    fout = fopen( FOUT, "w" );   
    fscanf( fin, "%d\n", &N );   
    for( i = 1; i <= N; i++ ) fscanf( fin, "%d %d\n", &gext[i], &gint[i] );   
    sursa = 1; dest = 2 * N + 2;   
    memset( CAP, 0, sizeof(CAP) );   
    memset( FLOW, 0, sizeof(FLOW) );   
    for( i = 2; i <= N + 1; i++ ) CAP[sursa][i] = gext[i-1];   
    for( i = N + 2; i < dest; i++) CAP[i][dest] = gint[i-N-1];   
    for( i = 2; i <= N + 1; i++)   
        for( j = N + 2; j < dest; j++ )  CAP[i][j] = 1;   
    for( i = 2; i <= N + 1; i++ ) CAP[i][i+N] = 0;   
    flow = 0;   
    do     
    {   
        BFS(sursa);   
        if (SEL[dest])    
        {   
            flow++;   
            RELAX(dest);   
        }   
    }while(SEL[dest]);   
    fprintf( fout, "%d\n", flow );   
    for( i = 2; i <= N + 1; i++)   
        for( j = N + 2; j < dest; j++)   
            if (FLOW[i][j]) fprintf( fout, "%d %d\n", i - 1, j - N - 1 );   
    fclose(fin);   
    fclose(fout);   
    return 0;   
}