Cod sursa(job #3190622)

Utilizator GFA03Gavrila Florin-Alexandru GFA03 Data 7 ianuarie 2024 19:23:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <vector>
#include <iostream>
#include <fstream>
#include <climits>
#include <queue>

using namespace std;

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

vector<vector<int>> capacity, flow, adj;
int source, target, n;
vector<int> parent;
const int INF = INT_MAX;

int bfs()
{
    for (int i = 0; i < capacity.size(); i++)
        parent[i] = -1;

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

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

        for (auto &neigh : adj[currentNode])
        {
            if (parent[neigh] == -1 && capacity[currentNode][neigh] > flow[currentNode][neigh])
            {
                parent[neigh] = currentNode;
                int residualFlow = capacity[currentNode][neigh] - flow[currentNode][neigh];
                int bottleneck = min(currentFlow, residualFlow);
                if (neigh == target)
                    return bottleneck;
                q.push({neigh, bottleneck});
            }
        }
    }
    return 0;
}

int maxflow()
{
    int newFlow;
    int flowSum = 0;
    parent.resize(target + 1);
    while (true)
    {
        newFlow = bfs();
        if (newFlow == 0)
            break;
        flowSum += newFlow;

        int currentNode = target;
        while (currentNode != source)
        {
            int parentNode = parent[currentNode];
            flow[parentNode][currentNode] += newFlow;
            flow[currentNode][parentNode] -= newFlow;
            currentNode = parentNode;
        }
    }
    return flowSum;
}

void read()
{
    fin >> n;
    source = 0;
    target = 2 * n + 1;
    capacity.resize(target + 1, vector<int>(2 * n + 2));
    flow.resize(target + 1, vector<int>(2 * n + 2));
    adj.resize(target + 1);

    int paths = 0;
    int x, y;

    for (int i = 1; i <= n; ++i)
    {
        // x - out degree, y - in degree
        fin >> x >> y;
        paths += x;
        capacity[source][i] = x;
        capacity[n + i][target] = y;
        adj[source].push_back(i);
        adj[i].push_back(source);
        adj[n + i].push_back(target);
        adj[target].push_back(n + i);
        for (int j = 1; j <= n; ++j)
        {
            if (i != j)
            {
                capacity[i][n + j] = 1;
                adj[i].push_back(n + j);
                adj[n + j].push_back(i);
            }
        }
    }
    fout << paths << '\n';
}

int main()
{
    read();
    int maximumFlow = maxflow();
    cout << maximumFlow << '\n';

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