Cod sursa(job #3188292)

Utilizator radubigColtos Radu radubig Data 2 ianuarie 2024 16:28:48
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
//#define LOCAL_TESTING

#include <fstream>
#include <vector>
#include <queue>

#ifdef LOCAL_TESTING
#define in_file "input.txt"
#define out_file "output.txt"
#else
#define in_file "harta.in"
#define out_file "harta.out
#endif

using namespace std;

vector<vector<int>> capacity;
vector<vector<int>> flux;
vector<bool> visited;
vector<int> parent;

void flux_init(size_t size)
{
    parent.resize(size, -1);
    visited.resize(size);
    flux.resize(size, vector<int>(size, 0));
    capacity.resize(size, vector<int>(size, 0));
}

bool bfs(int n)
{
    queue<int> q;
    q.push(2 * n);
    visited[2 * n] = true;

    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        for(int i = 0; i <= 2 * n + 1; i++)
            if(!visited[i] && capacity[node][i] - flux[node][i] > 0)
            {
                q.push(i);
                parent[i] = node;
                visited[i] = true;
            }
    }

    return visited[2 * n + 1];
}

int get_max_flow(int n)
{
    int flux_maxim = 0;
    const int t = 2 * n + 1;
    while(bfs(n))
    {
        int min_capacity = 2e9;
        int node1 = parent[t];
        int node2 = t;
        while(node1 != -1)
        {
            int c = capacity[node1][node2] - flux[node1][node2];
            if(c < min_capacity)
                min_capacity = c;
            node2 = node1;
            node1 = parent[node1];
        }

        node1 = parent[t];
        node2 = t;
        while(node1 != -1)
        {
            flux[node1][node2] += min_capacity;
            flux[node2][node1] -= min_capacity;
            node2 = node1;
            node1 = parent[node1];
        }

        flux_maxim += min_capacity;
        for(int j = 0; j <= t; j++)
            visited[j] = false;
    }
    return flux_maxim;
}

int main()
{
    ifstream in(in_file);
    ofstream out(out_file);

    int n;
    in >> n;
    flux_init(2 * n + 2);
    for(int i = 0; i < n; i++)
    {
        int x, y;
        in >> x >> y;
        capacity[2 * n][i] = x;
        capacity[i + n][2 * n + 1] = y;
        for(int j = 0; j < n; j++)
            if(i != j)
                capacity[i][j + n] = 1;
    }

    int flux_maxim = get_max_flow(n);
    out << flux_maxim << '\n';
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(flux[i][j + n] == 1)
                out << i+1 << ' ' << j+1 << '\n';
        }
    }

    in.close(); out.close();
    return 0;
}