Cod sursa(job #290169)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 27 martie 2009 16:29:15
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda aa Marime 1.97 kb
using namespace std;   
#include <cstdio>   
#include <algorithm>   
  
#define Nmax 256   
#define INF 1 << 30   
  
int N, n, M, C[Nmax][Nmax], F[Nmax][Nmax], t, c[Nmax], j, i, Min;   
int T[Nmax];   
  
void citire(){   
  
    int x, y, i;   
    FILE *f = fopen("harta.in", "r");   
       
    fscanf(f,"%d",&n);   
    N = 2*n + 1;   
    for(i=1; i<=n; i++){   
        fscanf(f,"%d %d",&x, &y);   
        M+=x;   
        C[0][i] = x; C[i+n][ N] = y;   
           
        for(j=n+1; j < N; j++)   
            if( i != j - n )   
                C[i][j] = 1;   
    }   
       
    fclose(f);   
}   
  
int BF(){   
  
    int p, u = 1, i, ok = 0;   
    memset(T, 0xff, (N+2) * sizeof(int));   
       
    c[1] = 0;   
    T[0] = 0;   
       
    for(p = 1; p <= u; p++)   
        for(i = 0; i <= N; i++){   
            if( C[c[p]][i] > F[c[p]][i] && T[i] == -1){   
                if( i == N ){ok =1 ; continue;}   
                c[++u] = i;   
                T[i] = c[p];   
            }   
        }   
       
    return ok;   
}   
  
void flux(){   
       
    while( BF() ){         
        for(i = n+1; i < N; i++){   
            if( T[i] ){   
                T[N] = i;   
                for(t = N, Min = INF; t != 0; t = T[t])   
                    Min = min (Min, C[T[t]][t] - F[T[t]][t] );   
                   
                for(t = N; t != 0; t = T[t])   
                    F[T[t]][t]+=Min ,F[t][T[t]]-=Min  ;   
                   
            }   
        }   
    }   
}   
  
  
void afisare(){   
  
    int i, j;   
    FILE *g = fopen("harta.out", "w");   
    fprintf(g,"%d\n",M);   
    for(i=1; i<=n; i++)   
        for(j = n+1; j < N ; j++)   
            if( i != (j - n) && F[i][j] > 0 )   
                fprintf(g,"%d %d\n",i, j-n);   
       
    fclose(g);   
}   
  
int main(){   
  
    citire();   
    flux();   
    afisare();   
  
    return 0;   
}