Cod sursa(job #2962270)

Utilizator DevCrutCorolevschi Mihai DevCrut Data 8 ianuarie 2023 05:08:01
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.86 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <string.h>
#include <string>
#include <sstream>
#include <climits>
#include <queue>

using namespace std;

int n, maxFlow;
int nodeCount;
vector<vector<pair<int, pair<int, int>>>> adjList;
vector<vector<int>> capacityMap;
vector<pair<int,int>> parentMap;

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

void ReadInputs() {
    myIn >> n;
    nodeCount = 2 * n + 2;


    adjList.resize(nodeCount, {});
    parentMap.resize(nodeCount, { -1,-1 });

    int in, out;
    for (int i = 1; i <= n; i++) {
        myIn >> in >> out;
        int indexA = adjList[0].size();
        int indexB = adjList[nodeCount - 1].size();
        int indexC1 = adjList[i].size();
        int indexC2 = adjList[n + i].size();

        adjList[0].push_back({ i,{ in,indexC1 } });
        adjList[i].push_back({ 0,{ 0,indexA } });

        adjList[nodeCount-1].push_back({ n + i,{ 0,indexC2} });
        adjList[n + i].push_back({ nodeCount - 1,{ out,indexB } });
    }
    for (int nodeA = 1; nodeA <= n; nodeA++) {
        for (int nodeB = 1; nodeB <= n; nodeB++) {
            if (nodeA == nodeB) continue;

            int offsetB = n + nodeB;
            int indexA = adjList[nodeA].size();
            int indexB = adjList[offsetB].size();

            adjList[nodeA].push_back({ offsetB,{ 1,indexB } });
            adjList[offsetB].push_back({ nodeA,{ 0,indexA } });
        }
    }

    //for (int node = 0; node < nodeCount; node++) {
    //    if (node == nodeCount - 1) {
    //        cout << "f: ";
    //    }
    //    else if (node == 0) {
    //        cout << "s: ";
    //    }
    //    else {
    //        cout << node << ": ";
    //    }

    //    for (int i = 0; i < adjList[node].size(); i++) {
    //        int newNode = adjList[node][i].first;
    //        if (newNode == nodeCount - 1) {
    //            cout << "f ";
    //        }
    //        else if (newNode == 0) {
    //            cout << "s ";
    //        }
    //        else {
    //            cout << newNode << " ";
    //        }
    //    }
    //    cout << "\n";
    //}
    //cout << "\n";
}

bool BFS() {
    for (int i = 0; i < parentMap.size(); i++) {
        parentMap[i].first = -1; parentMap[i].second = -1;
    }
    queue<int> q;
    q.push(0);

    while (not q.empty()) {
        int currentNode = q.front();
        q.pop();

        if (currentNode == nodeCount - 1) {
            return true;
        }

        for (int i = 0; i < adjList[currentNode].size(); i++) {
            auto nodeData = adjList[currentNode][i];
            int nextNode = nodeData.first;
            int capacity = nodeData.second.first;
            if ((parentMap[nextNode].first == -1) && (capacity > 0)) {
                q.push(nextNode);
                parentMap[nextNode] = { currentNode,i };
            }
        }
    }
    return false;
}

void EdmondsKarp() {
    int x = 0;
    while (BFS()) {
        for (int linkIndex = 0; linkIndex < adjList[nodeCount - 1].size(); linkIndex++) {
            auto linkData = adjList[nodeCount - 1][linkIndex];
            int sinkNode = linkData.first;

            if (parentMap[sinkNode].first != -1) {
                parentMap[nodeCount - 1].first = sinkNode;
                parentMap[nodeCount - 1].second = linkData.second.second;
                int minFlow = INT_MAX;
                for (int node = (nodeCount - 1); node != 0; node = parentMap[node].first) {
                    int adjNode = parentMap[node].first;
                    auto prevNodeLink = adjList[adjNode][parentMap[node].second];
                    minFlow = min(minFlow, prevNodeLink.second.first);
                }
                if (minFlow <= 0) continue;

                for (int node = (nodeCount - 1); node != 0; node = parentMap[node].first) {
                    int adjNode = parentMap[node].first;

                    (adjList[node][(adjList[adjNode][parentMap[node].second]).second.second]).second.first += minFlow;
                    (adjList[adjNode][parentMap[node].second]).second.first -= minFlow;
                }

                maxFlow += minFlow;
            }
        }
    }
}

void Output() {
    myOut << maxFlow << '\n';
    for (int i = 0; i < parentMap.size(); i++) {
        parentMap[i].first = 0;
    }
    parentMap[0].first = 1;
    parentMap[nodeCount - 1].first = 1;
    for (int node = 1; node <= n; node++) {
        for (int i = 0; i < adjList[node].size(); i++) {
            int newNode = adjList[node][i].first;
            if (((newNode - n) != node) && (newNode != 0) && (adjList[node][i].second.first != 1))
                myOut << node << ' ' << newNode - n << '\n';
        }
        parentMap[node].first = 1;
    }
}

int main() {
    ReadInputs();
    EdmondsKarp();
    Output();
}