Cod sursa(job #3179780)

Utilizator Alex_Cristea72Cristea Alexandru Alex_Cristea72 Data 4 decembrie 2023 10:47:33
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include<climits>
using namespace std;

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

int n;
vector<vector<int>> lista(305);
int cap[205][205];
int cap_init[205][205];
int viz[205], tata[205];

int bfs() {
    queue<int> coada;
    coada.push(0);

    for (int i = 0; i <= 2 * n + 1; i++) {
        tata[i] = -1;
        viz[i] = 0;
    }

    viz[0]++;

    while (!coada.empty()) {
        int nod_cur = coada.front();
        if (nod_cur == 2 * n + 1)
            return 1;

        for (int i = 0; i < lista[nod_cur].size(); i++) {
            int nod_vec = lista[nod_cur][i];
            if (cap[nod_cur][nod_vec] > 0 && viz[nod_vec] == 0) {
                viz[nod_vec]++;
                tata[nod_vec] = nod_cur;
                coada.push(nod_vec);
            }
        }
        coada.pop();
    }
    return 0;
}

int Edmonds_Karp() {
    int max_flux = 0;

    while (bfs()) {
        for (int i = 0; i < lista[2 * n + 1].size(); i++) {
            int nod_cur = lista[2 * n + 1][i];
            if (cap[nod_cur][2 * n + 1] > 0 && viz[nod_cur]) {
                vector<int> drum;
                drum.push_back(nod_cur);

                while (tata[nod_cur] != -1) {
                    nod_cur = tata[nod_cur];
                    drum.push_back(nod_cur);
                }

                int minim = INT_MAX;

                for (int i = 0; i < drum.size(); i++)
                    if (i == 0)
                        minim = min(minim, cap[drum[i]][2 * n + 1]);
                    else
                        minim = min(minim, cap[drum[i]][drum[i - 1]]);

                max_flux += minim;

                for (int i = 0; i < drum.size(); i++) {
                    if (i == 0) {
                        cap[drum[i]][2 * n + 1] -= minim;
                        cap[2 * n + 1][drum[i]] += minim;
                    } else {
                        cap[drum[i]][drum[i - 1]] -= minim;
                        cap[drum[i - 1]][drum[i]] += minim;
                    }
                }
            }
        }
    }
    return max_flux;
}

int main() {
    fin >> n;

    for (int i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;

        lista[0].push_back(i);
        cap[0][i] = x;
        cap_init[0][i] = x;

        lista[n + i].push_back(2 * n + 1);
        lista[2 * n + 1].push_back(n + i);
        cap[n + i][2 * n + 1] = y;
        cap_init[n + i][2 * n + 1] = y;
    }

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

    fout << Edmonds_Karp() << "\n";

    for (int i = 1; i <= n; i++)
        for (int j = n + 1; j < 2 * n + 1; j++)
            if (cap_init[i][j] == 1 && cap[i][j] == 0)
                fout << i << " " << j - n << "\n";
}