Cod sursa(job #3332209)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 5 ianuarie 2026 00:38:54
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 205;

vector <int> g[nmax];

int n, in[nmax], out[nmax];
int rez;

int cap[nmax][nmax], flow[nmax][nmax], t[nmax];
bool viz[nmax];

bool bfs (int s, int dest)
{
    for (int i = 0; i <= 2 * n + 1; i++)
        viz[i] = false;

    queue <int> q;
    viz[s] = true;
    q.push (s);

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

        for (auto x : g[node])
        {
            if (!viz[x] && cap[node][x] - flow[node][x] > 0)
            {
                viz[x] = true;
                t[x] = node;
                q.push (x);
            }
        }
    }

    return viz[2 * n + 1];
}

void compute_flow (int s, int dest)
{
    while (bfs (s, dest))
    {
        int sum = 1000;
        for (int i = dest; i != 0; i = t[i])
            sum = min (sum, cap[t[i]][i] - flow[t[i]][i]);

        for (int i = dest; i != 0; i = t[i])
        {
            flow[t[i]][i] += sum;
            flow[i][t[i]] -= sum;
        }
    }
}

int main ()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> out[i] >> in[i];
    for (int i = 1; i <= n; i++)
    {
        g[0].push_back (i);
        g[i].push_back (0);
        cap[0][i] = in[i];

        g[2 * n + 1].push_back (i + n);
        g[i + n].push_back (2 * n + 1);
        cap[i + n][2 * n + 1] = out[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
            {
                g[j].push_back (i + n);
                g[i + n].push_back (j);
                cap[j][i + n] = 1;
            }
        }
    }

    compute_flow (0, 2 * n + 1);

    vector <pair <int, int>> rez;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && cap[j][i + n] - flow[j][i + n] == 0)
                rez.push_back ({i, j});

    fout << rez.size () << '\n';
    for (auto it : rez)
        fout << it.first << " " << it.second << '\n';
    return 0;
}