Cod sursa(job #2662932)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 24 octombrie 2020 21:03:29
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda trainingflow Marime 2.02 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define f in
#define g out

using namespace std;
ifstream in ( "harta.in" );
ofstream out( "harta.out" );
int n, i, j, x, y, nod, dif, fluxmax, N;
int c[220][220], flux[220][220], t[220];
vector<int> L[220];
queue<int> q;
bitset<220> viz;

int bfs(){
    while ( !q.empty() )
        q.pop();
    viz.reset();
    viz[0] = 1;
    q.push(0);
    while ( !q.empty() ) {
        nod = q.front();
        for ( auto vecin: L[nod] )
            if ( !viz[vecin] && c[nod][vecin] > flux[nod][vecin] ){
                q.push(vecin);
                viz[vecin] = 1;
                t[vecin] = nod;
                if ( vecin == N )
                    return 1;
            }
        q.pop();
    }
    return 0;
}

int main() {
    f>>n;
    N = 2*n+1;
    for ( i=1; i <= n; i++ ){
        f>>x>>y;
        L[0].push_back(i);
        L[i].push_back(0);
        L[n+i].push_back(N);
        L[N].push_back(n+i);
        c[0][i] = x;
        c[n+i][N] = y;
    }
    for ( i=1; i <= n; i++ )
        for ( j=n+1; j < N; j++ )
            if ( j-i != n ){
                L[i].push_back(j);
                L[j].push_back(i);
                c[i][j] = 1;
            }
    
    while (bfs()) {
        for ( auto vecin: L[N] ){
            dif = c[vecin][N] - flux[vecin][N];
            if ( viz[vecin] && dif > 0 ){
                x = vecin;
                while ( t[x] > 0 ) {
                    dif = min ( dif, c[t[x]][x]-flux[t[x]][x] );
                    x = t[x];
                }
                flux[vecin][N] += dif;
                flux[N][vecin] -= dif;
                fluxmax += dif;
                x = vecin;
                while ( t[x] > 0 ) {
                    flux[t[x]][x] += dif;
                    flux[x][t[x]] -= dif;
                    x = t[x];
                }
            }
        }
    }
    g<<fluxmax<<"\n";
    for ( i=1; i <= n; i++ )
        for ( j=n+1; j < N; j++ )
            if ( flux[i][j] == 1 )
                g<<i<<" "<<j-n<<"\n";
    return 0;
}