Cod sursa(job #3188771)

Utilizator stefanmo03Mocanu Stefan stefanmo03 Data 3 ianuarie 2024 20:04:16
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include<vector>
#include<tuple>
#include<queue>

#include <fstream>
std::ifstream cin("harta.in");
std::ofstream cout("harta.out");

//#include <iostream>
//using namespace std;

class flux{
    int n;
    std::vector<std::vector<int>> cap,adi;
    int BFS(int start, int stop, std::vector<int> &tata){
        fill(tata.begin(),tata.end(),-1);
        tata[start] = -2;
        std::queue<std::pair<int,int>> q;
        q.emplace(start,INT_MAX);

        while(!q.empty()){
            int v = q.front().first;
            int f = q.front().second;
            q.pop();

            for(auto vecin: adi[v]){
                if(tata[vecin]==-1 && cap[v][vecin]){
                    tata[vecin] = v;
                    int flux_nou = min(f,cap[v][vecin]);
                    if(vecin == stop){
                        return flux_nou;
                    }
                    q.emplace(vecin,flux_nou);
                }
            }
        }
        return 0;
    }
public:
    flux(int n,
         std::vector<std::vector<int>> &cap,
         std::vector<std::vector<int>> &adi):
            n(n),cap(cap),adi(adi){}

    int flux_maxim(int start, int stop){
        int f = 0;
        std::vector<int> tata(2*n+2);
        int flux_nou;
        flux_nou = BFS(start,stop,tata);
        while(flux_nou){

            f += flux_nou;
            int v = stop;
            while(v != start){
                int ant = tata[v];
                cap[ant][v] -= flux_nou;
                cap[v][ant] += flux_nou;
                v = ant;
            }
            flux_nou = BFS(start,stop,tata);
        }
        return f;
    }
    void afis(int start, int stop){
        int maxi = flux_maxim(start,stop);
        cout<<maxi<<"\n";
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j)continue;
                if(cap[i][j+n]==0)cout<<i<<" "<<j<<"\n";
            }
        }

    }
};

int main() {
    int n;
    cin>>n;
    int start =0,stop = 2*n+1;
    std::vector<std::vector<int>> cap,adi;
    cap.resize(n*2+2,std::vector<int>(n*2+2,0));
    adi.resize(n*2+2,std::vector<int>());
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) {
            if(i==j)continue;
            cap[i][j + n] = 1;
            adi[i].push_back(j + n);
            adi[j + n].push_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        int x,y;
        cin >> x >> y;
        cap[start][i] = x;
        cap[i + n][stop] =y;
        adi[i].push_back(start);
        adi[start].push_back(i);
        adi[i + n].push_back(stop);
        adi[stop].push_back(i + n);
    }

    flux x(n,cap,adi);
    x.afis(start,stop);


    return 0;
}