Cod sursa(job #2956110)

Utilizator vladadAndries Vlad Andrei vladad Data 18 decembrie 2022 16:23:33
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int root, dest, n, m, d1, d2, c, total, l, r;
int dad[202];
vector<vector<int>>v;
int flux[202][202];
bool viz[202];
bool bfs()
{
    queue<int>q;
    for (int i = 0; i <= 2*n+1; i++)
    {
        dad[i] = -1;
        viz[i] = 0;
    }
    viz[0] = 1;
    q.push(0);
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for(auto next : v[node])
        {
            if(viz[next] == 0 && flux[node][next] > 0)
            {
                dad[next] = node;
                q.push(next);
                viz[next] = 1;
                if(next == 2 * n + 1)
                    return 1;
            }
        }
    }
    return 0;

}

int main()
{
    f >> n;
    v.resize(2*n + 2);
    for (int i = 1; i <= n; i++)
    {
        f >> d1 >> d2;
        flux[0][i] = d1;
        flux[n + i][2 * n + 1] = d2;
        v[0].push_back(i);
        v[i].push_back(0); ///conectam cu sursa
        v[n + i].push_back(2 * n + 1);
        v[2 * n + 1].push_back(n + i); ///conectam cu terminalul
        for (int j = n + 1; j <= 2 * n; j++)
            if (j - i != n) /// nu conectam i cu i (nu facem bucle)
            {
                v[i].push_back(j);
                v[j].push_back(i);
                flux[i][j] = 1;
            }
    }
    while (bfs())
        for (auto next : v[n])
        {
            if (!viz[next])
                continue;
            int minim = 2;
            int t = 2 * n + 1;
            while (t != 0)
            {
                minim = min(minim, flux[dad[t]][t]);
                t = dad[t];
            }
            t = 2 * n + 1;
            while (t != 0)
            {
                flux[dad[t]][t] -= minim;
                flux[t][dad[t]] += minim;
                t = dad[t];
            }
            total = total + minim;
        }
    g << total << '\n';
    for(int i = 1; i <= n; i++)
        for(int j = n + 1; j <= 2 * n + 1; j++)
            if (flux[j][i] == 1)
            {
                g << i << ' ' << j - n << '\n';
                continue;
            }

}