Cod sursa(job #2964565)

Utilizator SurtexXGheorghe Robert-Mihai SurtexX Data 13 ianuarie 2023 11:10:42
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <iterator>

using namespace std;

int n, max_flow;
vector<vector<int>> adjacence_list;
vector <vector <int>> cap;
vector <int> root;
ifstream f("harta.in");
ofstream g("harta.out");

bool bfs() {
    root = vector<int>(2 * n + 2, 0);
    vector<bool>visited(2 * n + 2);
    queue <int> q;
    q.push(0);
    visited[0] = true;
    while (!q.empty()) {
        int nod = q.front();
        q.pop();
        for (auto vecin : adjacence_list[nod]) {
            int current_cap = cap[nod][vecin];
            if (current_cap > 0 && !visited[vecin]) {
                root[vecin] = nod;
                if (vecin == 2 * n + 1)
                    return true;
                visited[vecin] = true;
                q.push(vecin);
            }
        }
    }
    return false;
}

int edmonds_karp_algorithm() {
    while (bfs()) {
        int current_flow = INT_MAX;
        int i = 2 * n + 1;
        while (i != 0) {
            current_flow = min(current_flow, cap[root[i]][i]);
            i = root[i];
        }

        i = 2 * n + 1;
        while (i != 0) {
            cap[root[i]][i] -= current_flow;
            cap[i][root[i]] += current_flow;
            i = root[i];
        }

        max_flow += current_flow;
    }
    return max_flow;
}

int main()
{
    int x, y;
    f >> n;
    adjacence_list = vector<vector<int>>(2*n+2);
    root = vector<int>(2*n+2, 0);
    cap = vector<vector<int>>(2 * n + 2, vector <int>(2 * n + 2, 0));
    for(int i=1;i<=n;i++)
        for (int j = n + 1;j <= 2 * n;j++) {
            if (i != j - n) {
                adjacence_list[i].push_back(j);
                adjacence_list[j].push_back(i);
                cap[i][j] = 1;
            }
        }
    for (int i = 1;i <= n;i++)
    {
        f >> x >> y;
        adjacence_list[0].push_back(i);
        adjacence_list[i].push_back(0);
        adjacence_list[2 * n + 1].push_back(i+n);
        adjacence_list[i+n].push_back(2 * n + 1);
        cap[0][i] = x;
        cap[i+n][2*n+1] = y;
    }
    g << edmonds_karp_algorithm() << endl;
    for (int i = 1;i <= n;i++)
        for (int j = n + 1;j <= 2 * n;j++)
            if (cap[j][i])
                g << i << " " << j - n << endl;
	return 0;
}