Cod sursa(job #3189536)

Utilizator DariusGhercaDarius Gherca DariusGherca Data 6 ianuarie 2024 09:12:47
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <bits/stdc++.h>

using namespace std;
const int N = 2e2 + 10, INF = INT_MAX;
int cap[N][N], n, S = 0, D, rez[N][N], val_rez;
vector <int> adc[N];

bool bfs(int src, int dst, vector<int> &parent, bitset<N> &viz){
    fill(parent.begin(), parent.end(), 0);
    viz.reset();
    queue <int> q;
//    bitset <N> viz;
    viz[src] = true;
    q.push(src);
    while(!q.empty()){
        int nact = q.front();
        q.pop();
        if(nact == dst)
            continue;
        for(auto adiacent: adc[nact]){
            if(rez[nact][adiacent] == cap[nact][adiacent] || viz[adiacent])
                continue;
            q.push(adiacent);
            parent[adiacent] = nact;
            viz[adiacent] = true;
        }
    }
//    cout << "BFS " << viz[dst] << "\n";
    return viz[dst];
}

void max_flux(int src, int dst){
    vector <int> parent(dst + 10);
    bitset <N> viz;
    while(bfs(src, dst, parent, viz)){
        for(auto adiacent: adc[dst]){
            if(rez[adiacent][dst] == cap[adiacent][dst] || !viz[adiacent])
                continue;
//            cout << adiacent << "\n";
            parent[dst] = adiacent;
            int aux = dst, val = N;
            while(aux != src){
//                int tata = parent[aux];
                val = min(val, cap[parent[aux]][aux] - rez[parent[aux]][aux]);
                aux = parent[aux];
            }
            if(!val)
                continue;
            aux = dst;
            while(aux != src){
//                cout << aux << " ";
//                int tata = parent[aux];
                rez[parent[aux]][aux] += val;
                rez[aux][parent[aux]] -= val;
                aux = parent[aux];
            }
//            cout << "\n";
            val_rez += val;
        }
    }
}

int main() {
    ifstream f("harta.in");
    ofstream g("harta.out");
    f >> n;
    D = 2 * n + 1;
    for(int i = 1; i <= n; i++) {
        int a, b;
        f >> a >> b;
        cap[S][i] = a;
        cap[n + i][D] = b;
        adc[S].push_back(i);
        adc[i].push_back(S);
        adc[n + i].push_back(D);
        adc[D].push_back(n + i);
        for (int j = 1; j <= n; j++) {
            if (i == j)
                continue;
            adc[i].push_back(j + n);
            adc[j + n].push_back(i);
            cap[i][j + n] = 1;
        }
    }
    max_flux(S, D);
    g << val_rez << "\n";
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(rez[i][j + n]){
                g << i << " " << j << "\n";
            }
        }
    }
    g.close();
    f.close();
    return 0;
}