Cod sursa(job #3189371)

Utilizator anamaria29sSuditu Ana-Maria anamaria29s Data 4 ianuarie 2024 22:45:00
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

const int INF = 1e9;

int n;
int capacity[202][202];
int parent[202];

bool bfs() {
    memset(parent, -1, sizeof(parent));

    queue<pair<int, int>> q;
    q.push({0, INF});
    parent[0] = 0;

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

        for (int nextNode = 0; nextNode <= 2 * n + 1; ++nextNode) {
            if (parent[nextNode] == -1 && capacity[currentNode][nextNode] > 0) {
                parent[nextNode] = currentNode;

                int newFlow = min(flow, capacity[currentNode][nextNode]);
                if (nextNode == 2 * n + 1) {
                    for (int node = nextNode; node != 0; node = parent[node]) {
                        capacity[parent[node]][node] -= newFlow;
                        capacity[node][parent[node]] += newFlow;
                    }
                    return true;
                }

                q.push({nextNode, newFlow});
            }
        }
    }

    return false;
}

int main() {
    fin >> n;

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

        capacity[0][i] = out;
        capacity[n + i][2 * n + 1] = in;

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

    int maxFlow = 0;

    while (bfs()) {
        ++maxFlow;
    }

    fout << maxFlow << '\n';

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (capacity[i][n + j] == 0 && i != j) {
                fout << i << ' ' << j << '\n';
            }
        }
    }
    return 0;
}