Cod sursa(job #2766662)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 2 august 2021 18:07:12
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>
#define NMAX 105

using namespace std;

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

int n, c[2 * NMAX][2 * NMAX], F[2 * NMAX][2 * NMAX], t[2 * NMAX];
bitset <2 * NMAX> v;
queue <int> q;
vector <int> edges[2 * NMAX];


bool bfs()
{
    bool ok = 0;
    for(int i = 0 ; i <= 2 * n + 1; i++)
        v[i] = 0;

    v[0] = 1;
    q.push(0);

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(auto k : edges[nod])
            if(c[nod][k] - F[nod][k] > 0 && !v[k])
            {
                v[k] = 1;
                t[k] = nod;
                q.push(k);
                if(k == 2 * n + 1)
                    ok = 1;
            }
    }

    return ok;
}

int main()
{
    f >> n;

    for(int i = 1; i <= n; i++)
    {
        int x, y;
        f >> x >> y;
        c[0][i] = x;
        c[i + n][2 * n + 1] = y;
        edges[0].push_back(i);
        edges[i].push_back(0);
        edges[i + n].push_back(2 * n + 1);
        edges[2 * n + 1].push_back(i + n);
        for(int j = 1; j <= n; j++)
            if(i != j)
            {
                c[i][j + n] = 1;
                edges[i].push_back(j + n);
                edges[j + n].push_back(i);
            }
    }

    int minim, flux = 0;
    while(bfs())
    {
        for(auto k : edges[2 * n + 1])
            if(v[k] && c[k][2 * n + 1] > F[k][2 * n + 1])
            {
                minim = c[k][2 * n + 1] - F[k][2 * n + 1];
                int p = k;
                while(p)
                {
                    minim = min(minim, c[t[p]][p] - F[t[p]][p]);
                    p = t[p];
                }
                flux += minim;

                F[k][2 * n + 1] += minim;
                F[2 * n + 1][k] -= minim;

                p = k;
                while(p)
                {
                    F[t[p]][p] += minim;
                    F[p][t[p]] -= minim;
                    p = t[p];
                }
            }
    }

    g << flux << "\n";
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(F[i][n + j] == 1)
                g << i << " " << j << "\n";


    return 0;
}