Cod sursa(job #2894657)

Utilizator Tudor06MusatTudor Tudor06 Data 28 aprilie 2022 00:48:14
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100;

vector <int> edges[2 * NMAX + 2];
int flux[2 * NMAX + 2][2 * NMAX + 2];
int p[2 * NMAX + 2];

int s, d, n;

bool bfs() {
    queue <int> q;
    for ( int i = 0; i <= 2 * n + 1; i ++ ) p[i] = -1;
    p[s] = -2;
    q.push( s );
    while ( !q.empty() ) {
        int node = q.front();
        q.pop();
        for ( auto it : edges[node] ) {
            if ( p[it] != -1 || flux[node][it] <= 0 ) continue;
            p[it] = node;
            q.push( it );
        }
    }
    return ( p[d] != -1 );
}
int main() {
    ifstream fin( "harta.in" );
    ofstream fout( "harta.out" );
    fin >> n;
    s = 0, d = 2 * n + 1;
    for ( int i = 1; i <= n; i ++ ) {
        int in, out;
        fin >> out >> in;

        edges[s].push_back( i );
        edges[i].push_back( s );
        flux[s][i] = out;
        flux[i][s] = 0;

        edges[d].push_back( i + n );
        edges[i + n].push_back( d );
        flux[i + n][d] = in;
        flux[d][i + n] = 0;
    }
    for ( int i = 1; i <= n; i ++ ) {
        for ( int j = n + 1; j <= 2 * n; j ++ ) {
            if ( i + n == j ) continue;
            edges[i].push_back( j );
            edges[j].push_back( i );
            flux[i][j] = 1;
        }
    }
    int flow = 0;
    while ( bfs() ) {
        for ( auto node : edges[d] ) {
            if ( flux[node][d] <= 0 || p[node] == -1 ) continue;
            int maxflow = flux[node][d];
            for ( int i = node; i != s; i = p[i] ) {
                maxflow = min( maxflow, flux[p[i]][i] );
            }
            flux[node][d] -= maxflow;
            flux[d][node] += maxflow;
            for ( int i = node; i != s; i = p[i] ) {
                flux[p[i]][i] -= maxflow;
                flux[i][p[i]] += maxflow;
            }
            flow += maxflow;
        }
    }
    fout << flow << '\n';
    for ( int i = 1; i <= n; i ++ ) {
        for ( int j = n + 1; j <= 2 * n; j ++ ) {
            if ( i + n != j && flux[i][j] == 0 )
                fout << i << ' ' << j - n << '\n';
        }
    }

    return 0;
}