Cod sursa(job #2960073)

Utilizator 0SiSBesliu Radu-Stefan 0SiS Data 3 ianuarie 2023 15:34:02
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Declare input and output files
ifstream f("harta.in");
ofstream g("harta.out");

int n, s, t;

vector < int > parent;
vector< vector < int >> capacity;
vector< vector < int >> adjNodeList;

bool bfs() {
    vector < bool > visited(t + 1);
    queue < int > q;

    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty()) {
        int firstInQueue = q.front();
        q.pop();
        
        for (auto const& adjNode: adjNodeList[firstInQueue]) {

            if (!visited[adjNode] && capacity[firstInQueue][adjNode]) {
                parent[adjNode] = firstInQueue;

                if ( adjNode == t) {
                    return true;
                }

                visited[adjNode] = true;
                q.push(adjNode);
            }
        }
    }

    return false;
}

int edmondsKarp() {
    int maxFlow = 0;

    while (bfs()) {
        int currentFlow = INT_MAX;
        
        for (int x = t; x!=s; x = parent[x]) {
            int y = parent[x];

            if (capacity[y][x] < currentFlow) {
                currentFlow = capacity[y][x];
            }
        }
        
        for (int x = t; x != s; x = parent[x]) {
            int y = parent[x];
            capacity[y][x] -= currentFlow;
            capacity[x][y] += currentFlow;
        }

        maxFlow += currentFlow;
    }
    
    return maxFlow;
}


int main() {
    f >> n;
    t = 2 * n + 1;

    adjNodeList.resize(t + 1);
    parent.resize(t + 1);
    capacity.resize(t + 1, vector < int >(t + 1));

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

        adjNodeList[s].push_back(i);
        adjNodeList[i].push_back(s);
        capacity[s][i] = x;

        adjNodeList[n + i].push_back(t);
        adjNodeList[t].push_back(n + i);
        capacity[n + i][t] = y;

    }

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

    g << edmondsKarp() << '\n';
    for (int i = 1; i <= n; ++i) {
        for (auto const& node: adjNodeList[i]) {
            if (node != s && !capacity[i][node] && node != t) {
                g << i << " " << node - n << '\n';
            }
        }
    }
    return 0;
}