Cod sursa(job #2936811)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 9 noiembrie 2022 16:42:44
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <iostream>

using namespace std;

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

const int max_size = 2e2 + 8, INF = 1e9 + 1;

int cap[max_size][max_size], t[max_size], intra[max_size], pleaca[max_size], n;
vector <int> mc[max_size];
bitset <max_size> viz;

bool bfs ()
{
    for (int i = 1; i <= 2 * n + 2; i++)
    {
        viz[i] = 0;
        t[i] = 0;
    }
    viz[1] = 1;
    queue <int> q;
    q.push(1);
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (auto f : mc[nod])
        {
            if (!viz[f] && cap[nod][f] > 0)
            {
                viz[f] = 1;
                t[f] = nod;
                if (f == 2 * n + 2)
                {
                    return true;
                }
                q.push(f);
            }
        }
    }
    return false;
}

int main ()
{
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> pleaca[i] >> intra[i];
    }
    for (int i = 1; i <= n; i++)
    {
        mc[1].push_back(i + 1);
        mc[i + 1].push_back(1);
        mc[i + n + 1].push_back(2 * n + 2);
        mc[2 * n + 2].push_back(i + n + 1);
        cap[1][i + 1] = pleaca[i];
        cap[i + n + 1][2 * n + 2] = intra[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
            {
                mc[i + 1].push_back(j + n + 1);
                mc[j + n + 1].push_back(i + 1);
                cap[i + 1][j + n + 1] = 1;
            }
        }
    }
    int maxflow = 0;
    while (bfs())
    {
        //cout << "x"; afisare de proba
        for (auto f : mc[2 * n + 2])
        {
            if (!viz[f] || cap[f][2 * n + 2] <= 0)
                continue;
            int nod = 2 * n + 2, min1 = INF;
            t[nod] = f;
            while (nod != 1)
            {
                min1 = min(min1, cap[t[nod]][nod]);
                nod = t[nod];
            }
            if (min1 <= 0)
                continue;
            maxflow += min1;
            nod = 2 * n + 2;
            while (nod != 1)
            {
                cap[t[nod]][nod] -= min1;
                cap[nod][t[nod]] += min1;
                nod = t[nod];
            }
        }
    }
    out << maxflow << '\n';
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (cap[i + 1][j + n + 1] == 0 && cap[j + n + 1][i + 1] != 0)
            {
                out << i << " " << j << '\n';
            }
        }
    }
    in.close();
    out.close();
    return 0;
}