Cod sursa(job #2957468)

Utilizator kanyjmkSabau Eduard kanyjmk Data 22 decembrie 2022 17:35:13
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue> 
#include <climits>


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

int BFS(int& n, int& source, int& target, vector<vector<int>>& capacity, vector<int>& parent)
{
    vector<bool> visited(n+1, false);
    queue<pair<int, int>> bfs_q;
    bfs_q.push({source, INT_MAX});
    visited[source] = true;
    int min_flow;

    while(!bfs_q.empty())
    {
        int curr_v = bfs_q.front().first;
        int curr_flow = bfs_q.front().second;
        bfs_q.pop();
        
        for(int next = 1; next < n; next++)
            if(!visited[next] && capacity[curr_v][next] > 0)
            {
                visited[next] = true;               
                min_flow = min(curr_flow, capacity[curr_v][next]);
                parent[next] = curr_v;

                if(next == target)
                {
                    return min_flow;
                }

                bfs_q.push({next, min_flow});
            }
    }

   return 0;
}

int main()
{
    int n, flow, source, target, size;

    fin >> n;

    size = 2*n + 2;

    vector<vector<int>> capacity(size, vector<int>(size));
    vector<int> parent(size, -1);
    
    flow = 0;
    source = 0;
    target = size-1;

    for(int i = 1; i <= n; i++)
    {
        int in, out;
        fin >> out >> in;
        capacity[source][i] = out;
        capacity[i+n][target] = in;

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

    
    while(true)
    {
        int min_flow = BFS(size, source, target, capacity, parent);
        if(min_flow == 0)
            break;
        flow += min_flow;

        for(auto curr_v = target; curr_v != source; curr_v = parent[curr_v])
        {
            capacity[parent[curr_v]][curr_v] -= min_flow;
            capacity[curr_v][parent[curr_v]] += min_flow;
        }

    }

    fout << flow << '\n';

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

    return 0;
}