Cod sursa(job #2964380)

Utilizator erwin12511Brustur Erwin erwin12511 Data 12 ianuarie 2023 21:09:27
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

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

vector<int> a[205];
int n, s, d, sol, r[205][205], tata[205], in[205], out[205];
bool viz[205];
queue<int>q;

 bool bfs()
{
    int i, x, l;
    for (i = 1;i <= n;i++)
        viz[i] = 0, tata[i] = 0;
    q.push(s);
    viz[s] = 1;
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        l = a[x].size();
        for (i = 0;i < l;i++)
            if (viz[a[x][i]] == 0 && r[x][a[x][i]] > 0)
            {
                viz[a[x][i]] = 1;
                tata[a[x][i]] = x;
                q.push(a[x][i]);
            }
    }
    return viz[d];
}

void flux_maxim()
{
    int i, j, flow, l = a[d].size();
    while (bfs() != 0)
    {
        for (i = 0;i < l;i++)
            if (tata[a[d][i]] != 0 && r[a[d][i]][d] > 0)
            {
                flow = r[a[d][i]][d];
                for (j = a[d][i];j != s;j = tata[j])
                {
                    flow = min(flow, r[tata[j]][j]);
                    if (flow == 0)
                        break;
                }
                if (flow != 0)
                {
                    r[a[d][i]][d] -= flow;
                    r[d][a[d][i]] += flow;
                    for (j = a[d][i];j != s;j = tata[j])
                    {
                        r[tata[j]][j] -= flow;
                        r[j][tata[j]] += flow;
                    }
                    sol += flow;
                }
            }
    }
}

int main()
{
    int i, sum = 0, j, l, nn;
    fin >> n;
    nn = n;
    for (i = 1;i <= n;i++)
    {
        fin >> out[i] >> in[i];
        sum += in[i];
    }
    s = 2 * n + 1;
    d = 2 * n + 2;
    for (i = 1;i <= n;i++)
    {
        a[s].push_back(i);
        a[i].push_back(s);
        a[i + n].push_back(d);
        a[d].push_back(i + n);
        r[s][i] = out[i];
        r[i + n][d] = in[i];
        for (j = 1;j <= n;j++)
            if (i != j)
            {
                a[i].push_back(j + n);
                a[j + n].push_back(i);
                r[i][j + n] = 1;
            }
    }
    n = n * 2 + 2;
    flux_maxim();
    fout << sum << '\n';
    for (i = 1;i <= nn;i++)
    {
        l = a[i].size();
        for (j = 0;j < l;j++)
            if (a[i][j] <= 2 * nn && r[i][a[i][j]] == 0)
                fout << i << " " << a[i][j] - nn << '\n';
    }
    return 0;
}