Cod sursa(job #2593531)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 4 aprilie 2020 09:49:30
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ( "harta.in" );
ofstream g ( "harta.out" );

const int N = 102;
struct meme{
    int x, y;
}sol[N * N];
int in[N], out[N], C[2 * N][2 * N], F[2 * N][2 * N], n, tata[2 * N];
bool viz[2 * N];
vector < int > graph[2 * N];
queue < int > q;

bool bfs ( int start ){
    for ( int i = 1; i <= 2 * n + 1; i++ )
        viz[i] = tata[i] = 0;
    q.push ( start );
    viz[start] = 1;
    while ( !q.empty ( ) ){
        int node = q.front ( );
        q.pop ( );
        for ( int i = 0; i < graph[node].size ( ); i++ ){
            int new_node = graph[node][i];
            if ( viz[new_node] == 0 && F[node][new_node] < C[node][new_node] ){
                q.push ( new_node );
                tata[new_node] = node;
                viz[new_node] = 1;
            }
        }
    }
    return viz[2 * n + 1];
}

int main()
{   int i, k = 0, j;
    f >> n;
    for ( i = 1; i <= n; i++ ){
        f >> out[i] >> in[i];
    }
    for ( i = 1; i <= n; i++ ){
        C[0][i] = out[i];
        graph[0].push_back ( i );
        graph[i].push_back ( 0 );
        C[i + n][2 * n + 1] = in[i];
        graph[i + n].push_back ( 2 * n + 1 );
        graph[2 * n + 1].push_back ( n + i );
        for ( j = 1; j <= n; j++ ){
            if ( i != j ){
                C[i][n + j] = 1;
                graph[i].push_back ( n + j );
                graph[n + j].push_back ( i );
            }
        }
    }
    while ( bfs ( 0 ) == 1 ){
        for ( i = 0; i < graph[2 * n + 1].size ( ); i++ ){
            int x = graph[2 * n + 1][i];
            if ( C[x][2 * n + 1] == F[x][2 * n + 1] || viz[x] == 0 )
                continue;
            int Min = C[x][2 * n + 1] - F[x][2 * n + 1];
            int c = x;
            while ( x != 0 ){
                Min = min ( Min, C[tata[x]][x] - F[tata[x]][x] );
                x = tata[x];
            }
            x = c;
            F[x][2 * n + 1] += Min;
            F[2 * n + 1][x] -= Min;
            while ( x != 0 ){
                F[tata[x]][x] += Min;
                F[x][tata[x]] -= Min;
                x = tata[x];
            }
        }
    }
    for ( i = 1; i <= n; i++ ){
        for ( j = 0; j < graph[i].size ( ); j++ ){
            int node = graph[i][j];
            if ( node != 0 && F[i][node] == C[i][node] ){
                sol[++k].x = i;
                sol[k].y = node - n;
            }
        }
    }
    g << k << '\n';
    for ( i = 1; i <= k; i++ )
        g << sol[i].x << ' ' << sol[i].y << '\n';
    return 0;
}