Cod sursa(job #2594537)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 6 aprilie 2020 12:15:39
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 100;

int N;
int inDeg[NMAX + 2], outDeg[NMAX + 2];

int S, D;
vector <int> g[2 * NMAX + 5];
int capacity[2 * NMAX + 5][2 * NMAX + 5], flow[2 * NMAX + 5][2 * NMAX + 5];
int bef[2 * NMAX + 5];

queue <int> Q;
bool seen[2 * NMAX + 5];

bool bfs()
{
    for(int i = S; i <= D; i++)
        seen[i] = false;

    Q.push(S);
    seen[S] = true;

    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();

        for(auto it : g[node])
            if(!seen[it] && capacity[node][it] > flow[node][it])
            {
                seen[it] = true;
                bef[it] = node;
                Q.push(it);
            }
    }

    return seen[D];
}

int main()
{
    fin >> N;

    int roads = 0;

    for(int i = 1; i <= N; i++)
    {
        fin >> outDeg[i] >> inDeg[i];
        roads += outDeg[i];
    }

    fout << roads << '\n';

    S = 0, D = 2 * N + 1;

    for(int i = 1; i <= N; i++)
    {
        g[S].push_back(i);
        g[i].push_back(S);

        capacity[S][i] = outDeg[i];

        g[i + N].push_back(D);
        g[D].push_back(i + N);

        capacity[i + N][D] = inDeg[i];

        for(int j = 1; j <= N; j++)
            if(i != j)
            {
                g[i].push_back(j + N);
                g[j + N].push_back(i);

                capacity[i][j + N] = 1;
            }
    }

    while(bfs())
    {
        for(auto it : g[D])
        {
            int pumpFlo = capacity[it][D] - flow[it][D];

            for(int node = it; node != S; node = bef[node])
                pumpFlo = min(pumpFlo, capacity[bef[node]][node] - flow[bef[node]][node]);

            flow[it][D] += pumpFlo;
            flow[D][it] -= pumpFlo;

            for(int node = it; node != S; node = bef[node])
            {
                flow[bef[node]][node] += pumpFlo;
                flow[node][bef[node]] -= pumpFlo;
            }
        }
    }

    for(int i = 1; i <= N; i++)
        for(auto it : g[i])
            if(flow[i][it] == 1)
                fout << i << ' ' << it - N << '\n';

    return 0;
}