Cod sursa(job #2961914)

Utilizator biancar28Radulescu Alexia-Bianca biancar28 Data 7 ianuarie 2023 13:29:05
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n,x,y,s,d,noduri,c;
vector<int>viz;
vector<int>t;//vector de muchii care duc la nodurile respective
vector<vector<int>>indici; //vector de indici de muchii;
// indici[i] = vector de muchii care ies din i
vector<int>out;
vector<int>in;

struct muchie{
    int x,y,c,poz;
};
vector<muchie>M;

int BFS(){
    t.clear();
    t.resize(n);
    fill(viz.begin(), viz.end(), 0);

    queue<int>q;
    viz[s]=1;
    q.push(s);

    while(!q.empty()){
        int vf = q.front();
        q.pop();
        for(auto aux:indici[vf]){
            muchie mc = M[aux];
            if(!viz[mc.y] && mc.c>0){
                q.push(mc.y);
                viz[mc.y] = 1;
                t[mc.y] = aux;

                if(mc.y == d){
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    f>>n;
    noduri = n*2 + 2;
    s = 0;
    d = noduri-1;

    viz.resize(noduri);
    t.resize(noduri);
    indici.resize(noduri);
    in.resize(n+1);
    out.resize(n+1);

    for(int i=1;i<=n;i++){
        f>>x>>y;
        out[i]=x;//nr drumuri care ies din i
        in[i]=y;//nr drumuri care intra in i
    }

    int dim = 0;
    //creez drumurile posibile
    for(int i=1;i<=n;i++){
        for(int j=1+n;j<=n*2;j++){
            if(i!=j-n){//verific sa nu am drum de la i la i
                dim+=2;
                M.push_back({i,j,1,dim-1});
                M.push_back({j,i,0,dim-2});
                indici[i].push_back(dim-2);
                indici[j].push_back(dim-1);
            }
        }
    }

    //adaug drumuri de la o sursa 0 la fiecare oras
    //drumurile de la s la i au flux=dr care ies din i
    for(int i=1;i<=n;i++){
        dim+=2;
        M.push_back({s,i,out[i],dim-1});
        M.push_back({i,s,0,dim-2});
        indici[s].push_back(dim-2);
        indici[i].push_back(dim-1);
    }

    //adaug drumuri de la fiecare oras la o destinatie d
    //dr de la i la d au flux=dr care intra in i
    for(int i = 1+n; i<=n*2; i++){
        dim+=2;
        M.push_back({i,d,in[i-n],dim-1});
        M.push_back({d,i,0,dim-2});
        indici[i].push_back(dim-2);
        indici[d].push_back(dim-1);
    }

    c=0;
    while(BFS()){
        for(auto aux:indici[d]){//verific mai multe drumuri
            if(viz[M[aux].y] && M[M[aux].poz].c!=0){//M[aux].y=tatal lui d
                //M[M[aux].poz]=muchie care iese din tatal lui d
                int minim = INT_MAX;
                muchie mc = M[aux];
                t[d] = mc.poz;
                int nod = d;

                while(nod != s){
                    minim = min(minim, M[t[nod]].c);
                    nod = M[t[nod]].x;
                }
                c +=minim;
                nod = d;
                while(nod!=s){
                    M[t[nod]].c -= minim;
                    M[M[t[nod]].poz].c +=minim;
                    nod = M[t[nod]].x;
                }
            }
        }
    }
    g<<c<<"\n";

    for(auto aux: M){
        if(aux.c==0 && aux.x!=s && aux.y!=d && aux.x<aux.y){
            g<<aux.x << " " << aux.y-n<<"\n";
        }
    }

    return 0;
}