Cod sursa(job #2956025)

Utilizator StanCatalinStanCatalin StanCatalin Data 18 decembrie 2022 15:21:39
Problema Taramul Nicaieri Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int dim = 105;

int n, deg_in[2*dim], deg_out[2*dim];
vector<int> vec[dim];
int graf_rezidual[2*dim][2*dim];
queue<int> q;
int viz[2*dim];
int tata[2*dim];
int sursa, destinatie;

int BFS() {
    for (int i=0; i<=2*n+1; i++) {
        viz[i] = 0;
    }
    viz[sursa] = 1;
    q.push(sursa);
    tata[sursa] = -1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == destinatie) continue;
        for (auto y:vec[x]) {
            if (graf_rezidual[x][y] > 0 && !viz[y]) {
                viz[y] = 1;
                tata[y] = x;
                q.push(y);
            }
        }
    }
    return viz[destinatie];
}


int main() {
    in >> n;
    for (int i=1; i<=n; i++) {
        in >> deg_out[i] >> deg_in[i];
    }
    sursa = 0;
    destinatie = 2*n + 1;

    for (int i=1; i<=n; i++) {
        vec[sursa].push_back(i);
        vec[i].push_back(sursa);
        graf_rezidual[sursa][i] = deg_out[i];
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i != j) {
                vec[i].push_back(n + j);
                vec[n+j].push_back(i);
                graf_rezidual[i][n+j] = 1;
            }
        }
    }

    for (int i=1; i<=n; i++) {
        vec[i+n].push_back(destinatie);
        vec[destinatie].push_back(i+n);
        graf_rezidual[i+n][destinatie] = deg_in[i];
    }

    int maxflow = 0;
    int mini = INT32_MAX;
    while (BFS()) {
        for (auto y:vec[destinatie]) {
            mini = INT32_MAX;
            tata[destinatie] = y;
            for (int j = destinatie; j != sursa; j = tata[j]) {
                mini = min(mini, graf_rezidual[tata[j]][j]);
            }

            maxflow += mini;

            for (int j = destinatie; j != sursa; j = tata[j]) {
                graf_rezidual[tata[j]][j] -= mini;
                graf_rezidual[j][tata[j]] += mini;
            }
        }
    }

    out << maxflow << "\n";
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i != j && graf_rezidual[i][n+j] == 0) {
                out << i << " " << j << "\n";
            }
        }
    }
    return 0;
}