Cod sursa(job #960083)

Utilizator matei_cChristescu Matei matei_c Data 9 iunie 2013 18:48:30
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std ;

ifstream fin("harta.in");
ofstream fout("harta.out");

#define maxn 201

int N ;

int cap[maxn][maxn], ocupat[maxn][maxn] ;
int tata[maxn] ;

int sursa, destinatie ;

queue<int> coada ;

int bfs()
{
    bool ok = false ;

    for(int i = 1; i <= destinatie; ++i )
        tata[i] = -1 ;

    coada.push(sursa) ;
    tata[sursa] = 0 ;

    while( coada.empty() == false )
    {
        int nod = coada.front() ;
        coada.pop() ;

        for(int i = 0; i <= destinatie; ++i )
        {
            if( cap[nod][i] > ocupat[nod][i] && tata[i] == -1 )
            {
                if( i == destinatie )
                {
                    ok = true ;
                    continue ;
                }

                coada.push(i) ;
                tata[i] = nod ;
            }
        }
    }

    return ok ;
}

int main()
{
    fin >> N ;

    sursa = 0 ;
    destinatie = 2 * N + 1 ;

    int suma = 0 ;
    for(int i = 1; i <= N; ++i )
    {
        int x, y ;
        fin >> x >> y ;
        suma += x ;

        cap[sursa][i] = x ;
        cap[ i + N ][destinatie] = y ;

        for(int j = N + 1; j < destinatie; ++j )
            if( i != j - N )
                cap[i][j] = 1 ;
    }

    while( bfs() )
    {
        for(int i = N + 1; i < destinatie; ++i )
        {
            if( tata[i] )
            {
                tata[destinatie] = i ;
                int fmin = 100000000 ;

                int nod = destinatie ;
                while( nod != 0 )
                {
                    fmin = min( fmin, cap[ tata[nod] ][nod] - ocupat[ tata[nod] ][nod] ) ;
                    nod = tata[nod] ;
                }

                nod = destinatie ;
                while( nod != 0 )
                {
                    ocupat[ tata[nod] ][nod] += fmin ;
                    ocupat[nod][ tata[nod] ] -= fmin ;
                    nod = tata[nod] ;
                }
            }
        }
    }

    fout << suma << "\n" ;

    for(int i = 1; i <= N; ++i )
         for(int j = N + 1; j < destinatie; ++j )
              if( i != j - N && ocupat[i][j] > 0 )
                   fout << i << " " << j - N << "\n" ;

    return 0 ;
}