Cod sursa(job #2970136)

Utilizator BluThund3rRadu George BluThund3r Data 24 ianuarie 2023 12:35:58
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.42 kb
#include <bits/stdc++.h>
using namespace std;

class FlowNetwork {
    static const int inf;
    int n, m, s, t, maxFlow = 0;
    struct edge {
        int src, dst, capacity, flow;
        edge* back;
    };
    vector<vector<edge*>> adj;
    vector<edge*> parentEdge;
    void appendEdge(int x, int y, int capacity) {
        edge* e1 = new edge;
        edge* e2 = new edge;

        e1->back = e2;
        e2->back = e1;
    
        e1->src = x;
        e1->dst = y;
        e1->capacity = capacity;
        e2->flow = e1->flow = 0;
        e2->src = y;
        e2->dst = x;
        e2->capacity = 0;

        adj[x].push_back(e1);
        adj[y].push_back(e2);
    }

    // once computed, the value of the max flow is stored in the maxFlow variable
    void computeMaxFlow();

public:
    FlowNetwork(int _n, int _m, int source, int term, vector<tuple<int, int, int>>& edges);
    void changeSource(int _s) { s = _s; }
    void changeTerminal(int _t) { t = _t; }
    bool bfs(int src, int term);

    // returns the maxFlow; if it's not computed, it computes it and then returns it
    int getMaxFlow();
    vector<pair<int, int>> getMinCut();
    vector<pair<int, int>> findMatching();
};

const int FlowNetwork::inf = INT_MAX;

// If you want bipartite matching, you must give the capacity of 1 to all edges
// an edge from edges vector has the following form : (src, dst, capacity)
FlowNetwork::FlowNetwork(int _n, int _m, int source, int term, vector<tuple<int, int, int>>& edges): n(_n), m(_m), s(source), t(term) {
    adj.resize(n + 1);
    parentEdge.resize(n + 1);
    maxFlow = 0;

    int x, y, c;
    for(auto edge : edges) {
        x = get<0>(edge);
        y = get<1>(edge);
        c = get<2>(edge);
        appendEdge(x, y, c);
    }
}

bool FlowNetwork::bfs(int src, int term) {
    fill(parentEdge.begin(), parentEdge.end(), nullptr);
    queue<int> q;
    q.push(src);

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

        for(auto nextEdge : adj[currNode])  {
            int nextNode = nextEdge->dst;
            if(!parentEdge[nextNode] && nextEdge->capacity - nextEdge->flow > 0) {
                parentEdge[nextNode] = nextEdge;
                if(nextNode != term) {
                    q.push(nextNode);
                }
            }
        }
    }   

    return parentEdge[term] != nullptr;
}

void FlowNetwork::computeMaxFlow() {
    while(bfs(s, t)) {
        for(auto terminalEdge : adj[t]) {
            if(terminalEdge->back->capacity - terminalEdge->back->flow <= 0 || !parentEdge[terminalEdge->dst])        
                continue;
            
            parentEdge[t] = terminalEdge->back;
            int minValOnPath = inf;
            for(auto current = t; current != s; current = parentEdge[current]->src)
                minValOnPath = min(minValOnPath, parentEdge[current]->capacity - parentEdge[current]->flow);
            
            if(!minValOnPath)    
                continue;
            
            maxFlow += minValOnPath;
            
            for(auto current = t; current != s; current = parentEdge[current]->src) {
                parentEdge[current]->flow += minValOnPath;
                parentEdge[current]->back->flow -= minValOnPath;
            }
        }
    }
}

int FlowNetwork::getMaxFlow(){
    if(!maxFlow)
        computeMaxFlow();
    return maxFlow;
}

vector<pair<int, int>> FlowNetwork::getMinCut() {
    if(!maxFlow)
        computeMaxFlow();
    
    vector<bool> viz(n + 1);
    queue<int> q;
    q.push(s);
    viz[s] = true;

    vector<pair<int, int>> result;
    int currNode;
    while(!q.empty()){
        currNode = q.front();
        q.pop();

        for(auto nextEdge : adj[currNode]) {
            if(nextEdge->flow && nextEdge->capacity - nextEdge->flow == 0)
                result.push_back({nextEdge->src, nextEdge->dst});
            
            else if(!viz[nextEdge->dst] && nextEdge->capacity != 0) {
                q.push(nextEdge->dst);
                viz[nextEdge->dst] = true;
            }
        }
    }

    return result;
}

vector<pair<int, int>> FlowNetwork::findMatching() {
    if(!maxFlow)
        computeMaxFlow();

    vector<pair<int, int>> result;
    
    int nrLeft = (int) adj[s].size();

    for(auto sourceEdge : adj[s]) {
        int leftNode = sourceEdge->dst;
        for(auto edge : adj[leftNode]) {
            if(edge->dst == s)
                continue;
            if(edge->capacity - edge->flow == 0)
                result.push_back({leftNode, edge->dst});
        }
    }

    return result;
}

int main() {
    ifstream in("harta.in");
    ofstream out("harta.out");
    int n, m, x, y, c, e;
    vector<tuple<int, int, int>> edges;
    
    in >> n;
    for(int i = 1; i <= n; ++ i) {
        in >> x >> y;
        edges.push_back({0, i, x});
        edges.push_back({n + i, 2*n + 1, y});
    }

    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j) {
            if(i == j)
                continue;
            edges.push_back({i, n + j, 1});
        }
            
            

    FlowNetwork graph{2*n + 2, e, 0, 2*n + 1, edges};

    out << graph.getMaxFlow() << '\n';

    auto result = graph.findMatching();
    for(auto edge : result) 
        out << edge.first << " " << edge.second - n << '\n';

    return 0;
}