Cod sursa(job #2962886)

Utilizator a.dulumanDuluman Andrada-Georgiana a.duluman Data 9 ianuarie 2023 18:16:39
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
/*
Algoritm: Folosim Edmonds Karp pentru flow maxim cu BFS
- afisam doar muchiile saturate

-----> Complexitatea = O(n*m^2)
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define N 202

using namespace std;

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

int n, flow, maxflow, i, j, a, b, sink, cnode;
pair<int, int> nod;
vector<int> graph[N];
int capac[N][N];
int tata[N];
bool viz[N];

bool BFS()
{
    queue<pair <int, int>> myq;
    memset(tata, 0, (sink+1) * sizeof(int));
    memset(viz, false, (sink+1) * sizeof(bool));

    myq.push({0, INT_MAX});
    viz[0] = true;

    while(!myq.empty())
    {
        nod = myq.front();
        myq.pop();

        for(auto &vecin: graph[nod.first]){
            if(!viz[vecin] && capac[nod.first][vecin] > 0)
            {
                tata[vecin] = nod.first;
                viz[vecin] = true;
                flow = min(nod.second, capac[nod.first][vecin]);

                if(vecin == sink)
                    return true;

                myq.push({vecin, flow});
            }
        }
    }

    flow = 0;
    return false;
}

int main() {
    fin >> n;
    sink = 2 * n + 1;

    for(i = 1; i <= n; ++i){
        fin >> a >> b;
        graph[0].push_back(i);
        graph[i].push_back(0);
        capac[0][i] = a;

        graph[n+i].push_back(sink);
        graph[sink].push_back(n+i);
        capac[n+i][sink] = b;
    }

    for(i = 1; i<= n; ++i){
        for(j = n + 1; j < sink; ++j){
            if(j - i == n)
                continue;

            capac[i][j] = 1;
            graph[i].push_back(j);
            graph[j].push_back(i);
        }
    }

    while(BFS())
    {
        maxflow += flow;
        cnode = sink;

        while(cnode){
            capac[cnode][tata[cnode]] += flow;
            capac[tata[cnode]][cnode] -= flow;

            cnode = tata[cnode];
        }
    }

    fout << maxflow << '\n';
    for(i = 1; i <= n; ++i){
        for(j = n + 1; j < sink; ++j){
            if(capac[j][i] == 1)
                fout << i << ' ' << j - n << '\n';
        }
    }

    return 0;
}