Cod sursa(job #2662081)

Utilizator KPP17Popescu Paul KPP17 Data 23 octombrie 2020 14:47:42
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda trainingflow Marime 1.84 kb
#define fisier "harta"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const int S = 100, N = 2*S + 2, INF = 110000;
int C[N][N], T[N], n, s;
#include <vector>
std::vector<int> L[N];
#include <deque>
#include <bitset>
std::bitset<N> E;
bool bfs()
{
    E = 1;
    for (std::deque<int> D = {0}; D.size(); D.pop_front())
        for (int back: L[D.front()])
            if (not E[back] and C[D.front()][back])
            {
                D.push_back(back);
                E[back] = true;
                T[back] = D.front();
                if (back == n)
                    return true;
            }
    return false;
}
int main()
{
    in >> s;
    n = 2*s + 1;
    for (int i = 1; i <= s; i++)
        for (int j = 1; j <= s; j++)
            if (i != j)
            {
                C[i][s+j] = 1;
                L[i].push_back(s+j);
                L[s+j].push_back(i);
            }
    for (int i = 1; i <= s; i++)
    {
        int degIn, degOut;
        in >> degOut >> degIn;
        C[0][i] = degOut;
        C[s+i][n] = degIn;
        L->push_back(i);
        L[s+i].push_back(n);
        L[n].push_back(s+i);
    }
    int m = 0;
    while (bfs())
        for (int t: L[n])
            if (E[t] and C[t][n])
            {
                T[n] = t;
                int min = INF;
                for (int i = t; i; i = T[i])
                    min = std::min(min, C[ T[i] ][i]);
                m += min;
                for (int i = n; i; i = T[i])
                {
                    C[ T[i] ][i] -= min;
                    C[i][ T[i] ] += min;
                }
            }
    out << m << '\n';
    for (int i = 1; i <= s; i++)
        for (int j = 1; j <= s; j++)
            if (i != j and not C[i][s+j])
                out << i << ' ' << j << '\n';
}