Cod sursa(job #2970657)

Utilizator Carol2002Stanciu ioan Carol Carol2002 Data 25 ianuarie 2023 17:53:47
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<bits/stdc++.h>

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

using namespace std;

int n, d1, d2,total;

int tata[202];
vector<vector<int>>lista;
int g[202][202];
int lab[202];

bool BFS() {
    queue<int>q;
    for(int i = 0; i <= 2 * n + 1; i++){
        tata[i] = -1;
        lab[i] = 0;
    }
    lab[0] = 1;
    q.push(0);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto el : lista[x]){
            if(lab[el] == 0 && g[x][el] > 0){
                tata[el] = x;
                q.push(el);
                lab[el] = 1;
                if (el == 2*n+1){
                    return 1;
                }
            }
        }
    }
    return 0;

}

int main(){
    in >> n;
    lista.resize(2*n + 2);
    for(int i = 1; i <= n; i++){
        in >> d1 >> d2;
        g[0][i] = d1;
        g[n+i][2*n + 1] = d2;

        lista[0].push_back(i);
        lista[i].push_back(0);

        lista[n + i].push_back(2 * n + 1);
        lista[2 * n + 1].push_back(n + i);

        for(int j = n + 1; j <= 2 * n; j++){
            if(j - i == n){
                continue;
            }
            lista[i].push_back(j);
            lista[j].push_back(i);
            g[i][j] = 1;
        }
    }
    while(BFS()){
        for(auto element : lista[n]){
            if (!lab[element]) {
                continue;
            }
            int minim = 1e7 + 1;
            int v = 2 * n + 1;
            while(v != 0){
                minim = min(minim, g[tata[v]][v]);
                v = tata[v];
            }
            v = 2*n+1;
            while(v != 0){
                g[tata[v]][v] -= minim;
                g[v][tata[v]] += minim;
                v = tata[v];
            }
            total = total + minim;
        }

    }
    out << total << "\n";
    for(int i = 1; i <= n; i++){
        for(int j = n + 1; j <= 2 * n + 1; j++){
            if(g[j][i] == 1){
                out << i <<' '<< j - n << '\n';
                continue;
            }
        }
    }
    return 0;
}