Cod sursa(job #2959711)

Utilizator IRadu1529Radu Ionescu IRadu1529 Data 2 ianuarie 2023 14:07:03
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 3.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <fstream>
#include <set>
using namespace std;


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

#define N 201

int n, m, e, maxFlow;
int s, t;
vector<vector<int>> pairOfA(N);
int capacity[N][N];
vector<vector<int>> l(N, vector<int>());
vector<int> parent(N);
set<pair<int, int>> edges;
int inDegree[N], outDegree[N];
//O(N * M2)
int bfs(int s, int t) {
    parent[s] = -2; // orice != -1 si [0,n+m+1]
    queue<pair<int, int>> q;
    q.push({ s, 1e9 });

    while (!q.empty()) {
        int cur = q.front().first;
        int maxFlow = q.front().second;
        q.pop();

        for (int next : l[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                int bottleneck = min(maxFlow, capacity[cur][next]);
                if (next == t)
                    return bottleneck;
                q.push({ next, bottleneck });
            }
        }
    }

    return 0;
}

void read() {
    fin >> n;
    m = n;

    for (int i = 1; i <= n; i++)
        fin >> outDegree[i] >> inDegree[i];
}

int main() {

    read();

    s = 0; t = n + m + 1;


    for (int i = 1; i <= n; i++) { // concectam sursa la nodurile din A cu valoarea gradului de iesire
        l[s].push_back(i);
        l[i].push_back(s);
        capacity[s][i] = outDegree[i];
    }

    for (int i = n + 1; i <= n + m; i++) { // concectam nodurile din B la destinatie cu valoarea gradului de intrare
        l[i].push_back(t);
        l[t].push_back(i);
        capacity[i][t] = inDegree[i - n];
    }

    for(int i = 1; i <= n; i++)
        for (int j = n + 1; j <= n + m; j++) {
           
            if (j - n == i) // nu vrem muchie de la un nod la el insusi
                continue;

            l[i].push_back(j);
            l[j].push_back(i);
            capacity[i][j] = 1;
        }

    for (int i = 0; i <= n + m + 1; i++) // resetam parintii
        parent[i] = -1;

    int bottleneck;

    while (bottleneck = bfs(s, t)) { // cat mai sunt path uri care mai accepta flux
        maxFlow += bottleneck;
        int node = t;
        while (node != s) { // mergem inapoi pe path ul gasit 
            int prev = parent[node];           
            capacity[prev][node] -= bottleneck; // muchia de inaintare pierde din spatiu exact bottleneck
            capacity[node][prev] += bottleneck; // muchia de retur poate face undo cu exact bottleneck mai mult

            if (node > s && node < t && prev > s && prev < t) {
                if (prev < node) {
                    pairOfA[prev].push_back(node);

                }
                else {
                    for (int aux = 0; aux < pairOfA[node].size(); ++aux) // daca e muchie de intoarcere scot muchia prev->node
                        if (pairOfA[node][aux] == prev) {
                            pairOfA[node].erase(pairOfA[node].begin() + aux);
                            break;
                        }
                }
            }
            node = prev;
        }
        for (int i = 0; i <= n + m + 1; i++) // resetam parintii
            parent[i] = -1;     

    }
    fout << maxFlow << "\n";
    for (int i = 1; i <= n; i++)
        for(auto j : pairOfA[i])
            fout << i << " " << j - n << "\n";
    return 0;
}