Cod sursa(job #3189854)

Utilizator LionMan101Achim-Panescu Silvian LionMan101 Data 6 ianuarie 2024 16:21:22
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>

using namespace std;

const int MAX_NODES = 500;
const int INF = 0xffffff;

int capacity[MAX_NODES][MAX_NODES];
int flow[MAX_NODES][MAX_NODES];
vector<int> graph[MAX_NODES];
int parent[MAX_NODES];
bool visited[MAX_NODES];
int nodeCount, maxFlow, minCapacity;

int indegree[MAX_NODES];
int outdegree[MAX_NODES];

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

bool bfs(int source, int dest) {
    memset(visited, false, sizeof(visited));
    queue<int> bfsQueue;
    bfsQueue.push(source);
    visited[source] = true;

    while (!bfsQueue.empty()) {
        int current = bfsQueue.front();
        bfsQueue.pop();

        for (int neighbor : graph[current]) {
            if (!visited[neighbor] && capacity[current][neighbor] > flow[current][neighbor]) {
                bfsQueue.push(neighbor);
                parent[neighbor] = current;
                visited[neighbor] = true;
            }
        }
    }
    return visited[dest];
}

void augmentFlow(int dest) {
    for (int i = 0; i < graph[dest].size(); ++i) {
        int current = graph[dest][i];
        if (!visited[current] || capacity[current][dest] == flow[current][dest])
            continue;

        minCapacity = INF;
        for (int node = dest; node != 1; node = parent[node])
            minCapacity = min(minCapacity, capacity[parent[node]][node] - flow[parent[node]][node]);

        if (minCapacity == 0)
            continue;

        for (int node = dest; node != 1; node = parent[node]) {
            flow[parent[node]][node] += minCapacity;
            flow[node][parent[node]] -= minCapacity;
        }
        maxFlow += minCapacity;
    }
}

void initializeGraph() {
    fin >> nodeCount;
    int source = 1;
    int dest = nodeCount * 2 + 2;

    for (int i = 1; i <= nodeCount; ++i) {
        fin >> outdegree[i] >> indegree[i];
        capacity[source][i + 1] = outdegree[i];
        graph[source].push_back(i + 1);
        graph[i + 1].push_back(source);

        capacity[i + 1 + nodeCount][dest] = indegree[i];
        graph[i + 1 + nodeCount].push_back(dest);
        graph[dest].push_back(i + 1 + nodeCount);
    }

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

void calculateMaxFlow(int source, int dest) {
    maxFlow = 0;
    while (bfs(source, dest)) {
        augmentFlow(dest);
    }
}

vector<pair<int, int>> extractResultEdges(int nodeCount) {
    vector<pair<int, int>> resultEdges;
    for (int i = 1; i <= nodeCount; ++i) {
        for (int j = 1; j <= nodeCount; ++j) {
            if (i != j && flow[i + 1][j + nodeCount + 1] == 1) {
                resultEdges.push_back({i, j});
            }
        }
    }
    return resultEdges;
}

void writeResult(const vector<pair<int, int>>& resultEdges) {
    fout << resultEdges.size() << "\n";
    for (const auto& edge : resultEdges) {
        fout << edge.first << " " << edge.second << "\n";
    }
}

int main() {
    initializeGraph();
    calculateMaxFlow(1, nodeCount * 2 + 2);
    vector<pair<int, int>> resultEdges = extractResultEdges(nodeCount);
    writeResult(resultEdges);

    fin.close();
    fout.close();

    return 0;
}