Cod sursa(job #3191473)

Utilizator dariutTache Daria dariut Data 9 ianuarie 2024 19:22:37
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

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

const int MAX_N = 205;

int n;
vector<vector<int>> graph(MAX_N);
int capacity[MAX_N][MAX_N];
int initial_capacity[MAX_N][MAX_N];
int visited[MAX_N], parent[MAX_N];

int bfs() {
    queue<int> q;
    q.push(0);

    fill(begin(parent), end(parent), -1);
    fill(begin(visited), end(visited), 0);
    visited[0]++;

    while (!q.empty()) {
        int current_node = q.front();
        if (current_node == 2 * n + 1)
            return 1;

        for (int i = 0; i < graph[current_node].size(); i++) {
            int next_node = graph[current_node][i];
            if (capacity[current_node][next_node] > 0 && !visited[next_node]) {
                visited[next_node]++;
                parent[next_node] = current_node;
                q.push(next_node);
            }
        }
        q.pop();
    }
    return 0;
}

int edmondsKarp() {
    int max_flow = 0;

    while (bfs()) {
        for (int i = 0; i < graph[2 * n + 1].size(); i++) {
            int current_node = graph[2 * n + 1][i];
            if (capacity[current_node][2 * n + 1] > 0 && visited[current_node]) {
                vector<int> path;
                path.push_back(current_node);

                while (parent[current_node] != -1) {
                    current_node = parent[current_node];
                    path.push_back(current_node);
                }

                int min_capacity = INT_MAX;

                for (int i = 0; i < path.size(); i++)
                    if (i == 0)
                        min_capacity = min(min_capacity, capacity[path[i]][2 * n + 1]);
                    else
                        min_capacity = min(min_capacity, capacity[path[i]][path[i - 1]]);

                max_flow += min_capacity;

                for (int i = 0; i < path.size(); i++) {
                    if (i == 0) {
                        capacity[path[i]][2 * n + 1] -= min_capacity;
                        capacity[2 * n + 1][path[i]] += min_capacity;
                    }
                    else {
                        capacity[path[i]][path[i - 1]] -= min_capacity;
                        capacity[path[i - 1]][path[i]] += min_capacity;
                    }
                }
            }
        }
    }
    return max_flow;
}

int main() {
    fin >> n;

    for (int i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;

        graph[0].push_back(i);
        capacity[0][i] = x;
        initial_capacity[0][i] = x;

        graph[n + i].push_back(2 * n + 1);
        graph[2 * n + 1].push_back(n + i);
        capacity[n + i][2 * n + 1] = y;
        initial_capacity[n + i][2 * n + 1] = y;
    }

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

    fout << edmondsKarp() << "\n";

    for (int i = 1; i <= n; i++)
        for (int j = n + 1; j < 2 * n + 1; j++)
            if (initial_capacity[i][j] == 1 && capacity[i][j] == 0)
                fout << i << " " << j - n << "\n";

    return 0;
}