Cod sursa(job #3193715)

Utilizator IulianMohoneaMohonea Marius-Iulian IulianMohonea Data 15 ianuarie 2024 15:12:35
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 kb
#include "bits/stdc++.h"
using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int numNodes;
vector<vector<int>> flowCapacity;
vector<vector<int>> graph;
const int INF = 1e9;

int bfs(int source, int sink, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[source] = -2;
    queue<pair<int, int>> queue;
    queue.push({ source, INF });

    while (!queue.empty()) {
        int current = queue.front().first;
        int currentFlow = queue.front().second;
        queue.pop();

        for (int next : graph[current]) {
            if (parent[next] == -1 && flowCapacity[current][next]) {
                parent[next] = current;
                int newFlow = min(currentFlow, flowCapacity[current][next]);
                if (next == sink)
                    return newFlow;
                queue.push({ next, newFlow });
            }
        }
    }

    return 0;
}

int findMaxFlow(int source, int sink) {
    int totalFlow = 0;
    vector<int> parent(202);
    int newFlow;

    while (newFlow = bfs(source, sink, parent)) {
        totalFlow += newFlow;
        int currentNode = sink;
        while (currentNode != source) {
            int previousNode = parent[currentNode];
            flowCapacity[previousNode][currentNode] -= newFlow;
            flowCapacity[currentNode][previousNode] += newFlow;
            currentNode = previousNode;
        }
    }
    return totalFlow;
}

int main() {
    fin >> numNodes;
    int sourceNode = 0, sinkNode = numNodes + numNodes + 1;
    flowCapacity.resize(200, vector<int>(200, 0));
    graph.resize(200);
    for (int i = 1; i <= numNodes; ++i) {
        int out, in;
        fin >> out >> in;
        graph[sourceNode].push_back(i);
        flowCapacity[sourceNode][i] = out;

        graph[numNodes + i].push_back(sinkNode);
        flowCapacity[numNodes + i][sinkNode] = in;

        for (int j = 1; j <= numNodes; ++j) {
            if (i == j)
                continue;
            graph[i].push_back(numNodes + j);
            flowCapacity[i][numNodes + j] = 1;
            graph[numNodes + j].push_back(i);
        }
    }
    fout << findMaxFlow(sourceNode, sinkNode) << '\n';

    for (int i = 1; i <= numNodes; ++i) {
        for (int adjacentNode: graph[i]) {
            if (flowCapacity[i][adjacentNode] == 0) {
                fout << i << " " << adjacentNode - numNodes << '\n';
            }
        }
    }

    return 0;
}