Cod sursa(job #2959032)

Utilizator soda-popClinciu Diana soda-pop Data 29 decembrie 2022 17:43:50
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.24 kb
#include <fstream>
#include <queue>
#include <vector>
#include<climits>
using namespace std;

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

int BFS(int s, int N, vector<vector<int>> &adjList,
        vector<vector<int>> &adjListIn, vector<vector<int>> &flux,
        vector<vector<int>> &cost, vector<int> &tata) {
    queue<int> queue;
    vector<int> viz(N + 1, 0);

    for (int i = 0; i <= N; i++) tata[i] = 0;

    queue.push(s);
    viz[s] = 1;
    while (!queue.empty()) {
        int x;

        x = queue.front();
        queue.pop();

        for (auto it = adjList[x].begin(); it != adjList[x].end(); ++it) {
            int y;
            y = *it;
            if (viz[y] == 0 && flux[x][y] < cost[x][y]) {
                queue.push(y);
                viz[y] = 1;
                tata[y] = x;
                if (y == N) return 1;
            }
        }

        for (auto it = adjListIn[x].begin(); it != adjListIn[x].end(); ++it) {
            int y;
            y = *it;
            if (viz[y] == 0 && flux[y][x] > 0) {
                queue.push(y);
                viz[y] = 1;
                tata[y] = -x;
                if (y == N) return 1;
            }
        }
    }
    return 0;
}

int maxFlow(int N, int s, int t, vector<vector<int>> &adjList,
            vector<vector<int>> &adjListIn, vector<vector<int>> &flux,
            vector<vector<int>> &cost) {
    vector<int> tata(N + 1);
    int fluxMax = 0;

    while (BFS(s, N, adjList, adjListIn, flux, cost, tata)) {
        // calculam i(P) = capacitatea reziduala minima pe un arc de pe drumul
        // de adjList s adjList t determinat cu bf
        int iP = INT_MAX;  // i(P)
        t = N;
        while (t != s) {
            if (tata[t] >= 0) {  // arc direct - capacitate c(e)-flux(e)
                if (cost[tata[t]][t] - flux[tata[t]][t] < iP)
                    iP = cost[tata[t]][t] - flux[tata[t]][t];
                t = tata[t];
            } else {  // arc invers - capacitate flux(e)
                if (flux[t][-tata[t]] < iP) iP = flux[t][-tata[t]];
                t = -tata[t];
            }
        }

        // revizuim fluxul de-a lungul lantului determinat
        t = N;
        while (t != s) {
            if (tata[t] >= 0) {  // arc direct - creste fluxul cu iP
                flux[tata[t]][t] = flux[tata[t]][t] + iP;
                t = tata[t];
            } else {  // arc invers - scade fluxul cu iP
                flux[t][-tata[t]] = flux[t][-tata[t]] - iP;
                t = -tata[t];
            }
        }

        fluxMax += iP;  // creste valoarea fluxului cu iP
    }

    return fluxMax;
}

int main() {
    int n;

    // creaza retea
    in >> n;

    int s = 2*n + 1;
    int t = 2*n + 2;
    int N = 2 * n + 2;

    vector<vector<int>> adjList(N + 1);
    vector<vector<int>> adjListIn(N + 1);
    vector<vector<int>> flux(N + 1, vector<int>(N + 1, 0));
    vector<vector<int>> cost(N + 1, vector<int>(N + 1, 0));

    for (int x = 1; x <= n; x++) {
        adjList[s].push_back(x);
        adjListIn[x].push_back(s);
    }

    for (int x = 1; x <= n; x++)
        for (int y = n + 1; y <= 2 * n; y++) {
            if (x != y - n) {
                adjList[x].push_back(y);
                adjListIn[y].push_back(x);
                cost[x][y] = 1;
            }
        }

    for (int y = n + 1; y <= 2 * n; y++) {
        adjList[y].push_back(t);
        adjListIn[t].push_back(y);
    }

    int sumaGrade = 0;
    for (int i = 1; i <= n; i++) {
        int d1, d2;
        in >> d1 >> d2;
        sumaGrade += d1;
        cost[s][i] = d1;
        cost[i + n][t] = d2;
    }

    int fluxMax = maxFlow(N, s, t, adjList, adjListIn, flux, cost);

    if (fluxMax != sumaGrade) {
        out << "Nu se poate construi un graf cu gradele date\n";
    } else {
        out << fluxMax << '\n';
        for (int x = 1; x <= n; x++) {
            for (auto it = adjList[x].begin(); it != adjList[x].end(); ++it) {
                int y;
                y = *it;
                if (flux[x][y]) {
                    out << x << ' ' << y - n << '\n';
                }
            }
        }
    }

    out.close();
    in.close();
    return 0;
}