Cod sursa(job #3323175)

Utilizator Anul2024Anul2024 Anul2024 Data 17 noiembrie 2025 14:18:12
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
const int DIM = 202, DIMM = 10100;
struct muchie
{
    int nod, pos;
};
muchie t[DIM + 1];
vector <muchie> v[DIM + 1];
int n, m, dp[DIM + 1];
queue <int> q;
int sume, pos, c[2 * DIMM + 1], se[DIM / 2], si[DIM / 2];
void add_mch (int l, int r, int p)
{
    v[l].push_back ({r, m});
    m++;
    v[r].push_back ({l, m});
    c[m - 1] = p, c[m] = 0;
    m++;
}
void read ()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> se[i] >> si[i];
        sume += se[i];
        add_mch (1, 2 * i, se[i]);
        add_mch (2 * i + 1, 2 * n + 2, si[i]);
    }
    pos = m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
                add_mch (2 * i, 2 * j + 1, 1);
        }
    }
}
bool bfs ()
{
    for (int i = 0; i <= 2 * n + 2; i++)
        t[i] = {0, 0}, dp[i] = 0;
    q.push (1);
    dp[1] = sume;
    while (!q.empty ())
    {
        int nod = q.front ();
        q.pop ();
        for (int i = 0; i < (int) v[nod].size (); i++)
        {
            int vecin = v[nod][i].nod;
            int pos = v[nod][i].pos;
            if (dp[vecin] == 0 && c[pos])
            {
                t[vecin] = {nod, pos};
                q.push (vecin);
                dp[vecin] = min (c[pos], dp[nod]);
            }
        }
    }
    return dp[2 * n + 2];
}
void add_flux (int flux)
{
    int nod = 2 * n + 2;
    while (nod != 1)
    {
        c[t[nod].pos] -= flux;
        c[t[nod].pos ^ 1] += flux;
        nod = t[nod].nod;
    }
}
void solve ()
{
    int sol = 0;
    while (bfs ())
    {
        int flux = dp[2 * n + 2];
        add_flux (flux);
        sol += flux;
    }
    fout << sol << "\n";
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
            {
                if (c[pos] == 0)
                    fout << i << " " << j << "\n";
                pos += 2;
            }
        }
    }
}
int main ()
{
    read ();
    solve ();
    return 0;
}