Cod sursa(job #2958088)

Utilizator BluThund3rRadu George BluThund3r Data 24 decembrie 2022 16:13:07
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");

class Solution {
    int n, m, source, sink;
    vector<vector<int>> capacity, flow, adj;
    vector<bool> viz;
    vector<int> parent;

public:
    Solution(int _n, vector<pair<int, int>> degs, int src, int sink);
    bool bfs(int src);
    void findMap();
};

bool Solution::bfs(int src) {
    fill(viz.begin(), viz.end(), false);
    fill(parent.begin(), parent.end(), -1);
    queue<int> q;
    q.push(src);
    viz[src] = true;

    int currNode;
    while(!q.empty()) {
        currNode = q.front();
        q.pop();

        for(auto nextNode : adj[currNode]) 
            if(!viz[nextNode] && capacity[currNode][nextNode] - flow[currNode][nextNode] > 0) {
                viz[nextNode] = true;
                if(nextNode != sink) {
                    q.push(nextNode);
                    parent[nextNode] = currNode;
                }
            }
    }   

    return viz[n];  
} 

void Solution::findMap() {
    int maxFlow = 0;
    while(bfs(source)) {
        for(auto leaf : adj[sink]) {
            if(capacity[leaf][sink] - flow[leaf][sink] <= 0 || !viz[leaf])    
                continue;

            parent[sink] = leaf;
            int minValOnPath = 110000;
            for(int node = sink; parent[node] != -1; node = parent[node])
                minValOnPath = min(minValOnPath, capacity[parent[node]][node] - flow[parent[node]][node]);
            
            if(!minValOnPath)   
                continue;
            
            maxFlow += minValOnPath;

            for(int node = sink; parent[node] != -1; node = parent[node]) {
                flow[parent[node]][node] += minValOnPath;
                flow[node][parent[node]] -= minValOnPath;
            }
        }
    }

    cout << maxFlow << '\n';

    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            if(i == j)
                continue;
            if(capacity[i][n + j] - flow[i][n + j] == 0)
                cout << i << ' ' << j << '\n';
        }
          
    }
}

Solution::Solution(int _n, vector<pair<int, int>> degs, int src, int sink): n(_n), source(src), sink(sink) {
    adj.resize(sink + 1);
    viz.resize(sink + 1);
    parent.resize(sink + 1);
    capacity.resize(sink + 1, vector<int>(sink + 1, 0));
    flow.resize(sink + 1, vector<int>(sink + 1, 0));

    int degout, degin;
    for(auto i = 0; i < degs.size(); ++ i) {
        degout = degs[i].first; degin = degs[i].second;
        adj[source].push_back(i + 1);
        adj[i + 1].push_back(source);
        capacity[source][i + 1] = degout;
        adj[i + n + 1].push_back(sink);
        adj[sink].push_back(i + n + 1);
        capacity[i + n + 1][sink] = degin;
    }

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

int main() {
    vector<pair<int, int>> deg;
    int n, x, y;
    in >> n;
    for(int i = 0; i < n; ++ i) {
        in >> x >> y;
        deg.push_back({x, y});
    }

    Solution s(n, deg, 0, 2 * n + 1);
    s.findMap();
    return 0;
}