Cod sursa(job #2962928)

Utilizator DianaZaharia132nr2Zaharia Diana Cristiana DianaZaharia132nr2 Data 9 ianuarie 2023 19:59:55
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.46 kb
/*
Zaharia Diana Cristiana

Explicatie problema, idee + metoda de rezolvare :

- folosim algoritmul de la flux maxim ( bfs + fluxmaxim) si il adaptam problemei curente

- construim matricea grafului pt rularea alg de flux

- dublam nodurile( n+i este dublura lui i)  (avem 2*n nduri la final)


- adaugam muchii de la sursa la fiecare nod cu capacitatea egala cu gradul out  0 -> N ( sa vedem toate nodurile din
                                                                                        care se pleaca)

- adaugan muchii de la fiecare nod la destinatie cu cap egala cu gradul in  N+1 -> 2*N + 1
                                                                            (nodurile in care se vine)

- adaugam muchii de la fiecare nod la celelalte noduri (capacitatea = 1)  (fara legaturi cu el insusi)


- facem flux maxim -> fluxul maxim = nr de muchii adaugate (cap 1 pe muchie ne ajuta sa numaram)

 Muchiile afisate sunt cele cu capacitate = 0



*/

#include <bits/stdc++.h>

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

int N, x, y, fluxmax, gr[1001][1001], t[1001], in[1001], out[1001];
bool viz[1001];
queue <int> q;

bool bfs()
{
    while (q.empty() == false)
        q.pop();


    for (int i=0; i <= 2*N+1; i++){

        t[i] = -1;
        viz[i] = false;

    }

    q.push(0);
    viz[0] = true;

    while (q.empty() == false)
    {
        auto nd = q.front();
        q.pop();

        if (nd == 2*N + 1)
         return true;

        for (int i=1; i<= 2*N + 1; i++)
            if (viz[i] == false && gr[nd][i] > 0){

                q.push(i);
                t[i] = nd;
                viz[i] = true;

            }
    }


    return false;

}


int fluxtaram(){

 while(bfs()){

    for (int i=N+1; i < 2*N+1; i++){

        if (gr[i][2*N + 1] > 0 && viz[i] == true){
            int frz = i;

            vector <int> drm;
            drm.push_back(2*N + 1);
            drm.push_back(frz);
            int nd = t[frz];

            if (nd == 0)
                    drm.push_back(nd);

            else{

             while (nd != 0){

                drm.push_back(nd);
                nd = t[nd];

             }

                drm.push_back(0);

              }


            reverse(drm.begin(), drm.end());

            int capmin = 1000000;

            for(long long unsigned int i=0; i<drm.size()-1; i++)
             capmin = min(capmin, gr[drm[i]][drm[i+1]]);


            fluxmax = fluxmax + capmin;


            for(long long unsigned int i=0; i<drm.size()-1; i++){
                    gr[drm[i]][drm[i+1]] = gr[drm[i]][drm[i+1]] - capmin;
                    gr[drm[i+1]][drm[i]] = gr[drm[i+1]][drm[i]] + capmin;
            }


          }

        }

    }



 return fluxmax;
}



int main(){

    f >> N;
    // cin >> N;
    for (int i=1; i <= N; i++){
        f >> x >> y;
       // cin >> x >> y;
     out[i] = x;
     in[i] = y;
     gr[0][i] = out[i];
     gr[N+i][2*N+1] = in[i];

        for (int nd=1; nd <= N; nd++)
            if (nd != i)
                gr[i][N+nd] = 1;
    }

    fluxtaram();

    g << fluxmax << endl;
   // cout << fluxmax << endl;

    for (int i=1; i <= N; i++)
        for (int j=1; j<=N; j++)
         if (gr[i][N+j] == 0 && i != j){
            g << i << " " << j << endl;
            //cout << i << " " << j << endl;
         }

    return 0;
}