Cod sursa(job #159675)

Utilizator iondionGeorge Pascu iondion Data 14 martie 2008 12:18:34
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <fstream>
#define NMax 202
#define min(a,b) ( (a)<(b)?(a):(b) )
#define abs(x) ( (x)>0?(x):(-x) )
using namespace std;
int C[NMax][NMax], F[NMax][NMax];
int v[NMax], Q[NMax];
int n;

void citire()
{
     int i;
     ifstream fin("harta.in");
     fin >> n;
     for( i=1; i<=n; i++ )
          fin >> C[n+i][2*n+1] >> C[0][i];
     fin.close();
}

void init()
{
     int i, j;
     for( i=1; i<=n; i++ )
          for( j=1; j<=n; j++ )
               if( i!=j )
                   C[i][n+j]=1;
}

int bfs()
{
    int st, dr, i, x;
    Q[0]=0; st=dr=0; v[0]=1;
    while( st<=dr && !v[2*n+1] )
    {
          x = Q[st++];
          for( i=1; i<=2*n+1; i++ )
               if( !v[i] )
                   if( F[x][i] < C[x][i] )
                   {
                       v[i]=x;
                       Q[++dr]=i;
                   }
                   else if( F[i][x] > 0 )
                   {
                       v[i]=-x;
                       Q[++dr]=i;
                   }
    }
    return !v[2*n+1];
}

void ek()
{
     int i, a, b, flux, lg;
     int L[NMax];
     do
     {
         for( i=0; i<=2*n+1; i++ ) v[i]=0;
         if( bfs() ) return;
         L[0] = 2*n+1; lg=0;
         a = b = 200;
         while( L[lg]!=0 )
         {
                ++lg;
                L[lg] =  abs( v[L[lg-1]] );
                if( v[L[lg-1]] > 0 )
                    a = min( a, C[L[lg]][L[lg-1]] - F[L[lg]][L[lg-1]] );
                else if( v[L[lg-1]] < 0 )
                    b = min( b, F[L[lg-1]][L[lg]] );
         }
         flux = min( a, b );
         for( i=lg; i>0; i-- )
              if( v[L[i-1]]>0 )
                  F[L[i]][L[i-1]]+=flux;
              else
                  F[L[i-1]][L[i]]-=flux;
     }
     while( 1 );
}

void afisare()
{
     int i, j;
     ofstream fout("harta.out");
     int nrm=0;
     for( i=1; i<=n; i++ )
          nrm+=F[n+i][2*n+1];
     fout << nrm << '\n';
     for( i=1; i<=n; i++ )
          for( j=1; j<=n; j++ )
               if( F[i][n+j] )
                   fout << i << ' ' << j << '\n';
     fout.close();
}

int main()
{
    citire();
    init();
    ek();
    afisare();
    return 0;
}