Cod sursa(job #3188837)

Utilizator RaducusCaracas Radu Nicolae Raducus Data 3 ianuarie 2024 21:48:25
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>

using namespace std;

const int MAX_N = 210;
const int INF = INT_MAX;

int capacity[MAX_N][MAX_N];
int flowPassed[MAX_N][MAX_N];
vector<int> graph[MAX_N];
int parentsList[MAX_N];
int currentPathCapacity[MAX_N];

int bfs(int startNode, int endNode) {
    memset(parentsList, -1, sizeof(parentsList));
    memset(currentPathCapacity, 0, sizeof(currentPathCapacity));
    queue<int> q;
    q.push(startNode);
    parentsList[startNode] = -2;
    currentPathCapacity[startNode] = INF;

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

        for (int to : graph[currentNode]) {
            if (parentsList[to] == -1) {
                if (capacity[currentNode][to] - flowPassed[currentNode][to] > 0) {
                    parentsList[to] = currentNode;
                    currentPathCapacity[to] = min(currentPathCapacity[currentNode], 
                        capacity[currentNode][to] - flowPassed[currentNode][to]);

                    if (to == endNode) {
                        return currentPathCapacity[endNode];
                    }
                    q.push(to);
                }
            }
        }
    }
    return 0;
}

int edmondsKarp(int startNode, int endNode) {
    int maxFlow = 0;
    memset(flowPassed, 0, sizeof(flowPassed));

    while (true) {
        int flow = bfs(startNode, endNode);

        if (flow == 0) {
            break;
        }

        maxFlow += flow;
        int currentNode = endNode;
        while (currentNode != startNode) {
            int previousNode = parentsList[currentNode];
            flowPassed[previousNode][currentNode] += flow;
            flowPassed[currentNode][previousNode] -= flow;
            currentNode = previousNode;
        }
    }
    return maxFlow;
}

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

    int n;
    fin >> n;

    int source = 0, sink = 2 * n + 1;

    for (int i = 1; i <= n; ++i) {
        int out, in;
        fin >> out >> in;

        capacity[source][i] = out; 
        capacity[i + n][sink] = in; 

        graph[source].push_back(i);
        graph[i + n].push_back(sink);

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

    int maxFlow = edmondsKarp(source, sink);

    fout << maxFlow << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (flowPassed[i][j + n] > 0) {
                fout << i << " " << j << endl;
            }
        }
    }

    fin.close();
    fout.close();
    return 0;
}