Cod sursa(job #2298341)

Utilizator HumikoPostu Alexandru Humiko Data 8 decembrie 2018 01:06:54
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, maximum_flow;

int f[205];
int previous[205];
int capacity[205][205];
int flow[205][205];

vector <int> graph[205];

void reset()
{
    for ( int i = 0; i <= 205; ++i )
        f[i] = previous[i] = 0;
}

bool maximumFlow (int source)
{
    reset();

    queue <int> q;
    q.push(source);
    f[source] = 1;

    while ( q.size() )
    {
        int node = q.front();
        q.pop();

        if ( node == 2*n+1 ) continue;

        for ( auto x:graph[node] )
        {
            if ( !f[x] && capacity[node][x] > flow[node][x] )
            {
                q.push(x);
                f[x] = 1;
                previous[x] = node;
            }
        }
    }
    return f[2*n+1];
}

int main ()
{
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);

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

        graph[i].push_back(0);
        graph[0].push_back(i);
        capacity[0][i] = x;

        graph[i+n].push_back(2*n+1);
        graph[2*n+1].push_back(i+n);
        capacity[i+n][2*n+1] = y;

        for ( int j = 1; j <= n; ++j )
        {
            if ( i == j ) continue;

            graph[i].push_back(j+n);
            graph[j+n].push_back(i);
            capacity[i][j+n] = 1;
        }
    }

    while ( maximumFlow(0) )
    {
        for ( auto x:graph[2*n+1] )
        {
            if ( f[x] && capacity[x][2*n+1] > flow[x][2*n+1] )
            {
                previous[2*n+1] = x;
                int aux = 2*n+1;
                int minimum = 1e9;

                while ( aux )
                {
                    minimum = min(minimum, capacity[previous[aux]][aux]-flow[previous[aux]][aux]);
                    aux = previous[aux];
                }

                aux = 2*n+1;

                while ( aux )
                {
                    flow[aux][previous[aux]] -= minimum;
                    flow[previous[aux]][aux] += minimum;
                    aux = previous[aux];
                }

                maximum_flow += minimum;
            }
        }
    }

    fout<<maximum_flow<<'\n';
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
            if ( i != j && flow[i][j+n] > 0 )
                fout<<i<<" "<<j<<'\n';
}