Cod sursa(job #2967173)

Utilizator maria-marianita.cucos@s.unibuc.roCucos Marianita [email protected] Data 19 ianuarie 2023 10:09:27
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.65 kb

//  vf intrare/iesire
// Complexitate: O(m*n^2)

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

int c[1024][1024]; // capacitate intre doua noduri
int f[1024][1024]; // flux (capacitate consumata)
int tata[1024]; // tatal fiecarui nod
vector<int> la[1024];
vector<int> vizitat;
int nod,n,m,x,y,z,i,j,minn,flow,sursa,destinatie;

int bfs()
{
    vizitat.assign(n+n+2, 0);
    queue<int> coada;
    coada.push(0); // sursa
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop();
        vizitat[nod]=1;
        if(nod == n+n+1) break; //opresc parcurgerea daca ajung la destinatie
        for(int j=0;j<la[nod].size();j++)
        {
            if(vizitat[la[nod][j]]==0 && c[nod][la[nod][j]]!=f[nod][la[nod][j]]) //daca nu e vizitat si daca drumul nu a fost consumat
            {
                coada.push(la[nod][j]);
                vizitat[la[nod][j]]=1;
                tata[la[nod][j]]=nod; //retin tatal nodului
            }
        }
    }
    return vizitat[n];//ne zice daca a ajuns la final drumul -> nu s a gasit fluxul maxim deci continuam
}

int main()
{
    fin>>n;
    sursa=0;
    destinatie=n+n+1;
    ///dublez nodurile
    for(i =1;i<=n;i++)
    {
        fin>>x>>y;
        la[sursa].push_back(i);
        la[i].push_back(sursa);
        la[destinatie].push_back(n+i);
        la[n+i].push_back(destinatie);
        c[0][i] =x;
        c[i+n][n+n+1]=y;
    }

    for(i =1;i<=n;i++)
    {
        for(j=1+n;j<=n+n;j++)
        {
            if(i!=j-n) //intre nod si dublura lui nu e muchie
            {
                c[i][j]=1;//intre oricare nod si alta dublura am muchie
                la[i].push_back(j);
                la[j].push_back(i);
            }
        }
    }

    flow=0;
    while(bfs())
    {
        for(i=0;i<la[n+n+1].size();i++) // muchiile cu care ajung in destinatie
        {
            nod = la[n+n+1][i];
            if (f[nod][n+n+1] == c[nod][n+n+1] || !vizitat[nod])  // drum saturat sau nu a fost vizitat
                continue;
            tata[n+n+1] = nod;
            int minn=9999999;
            for (j =n+n+1; j>0; j = tata[j])
            {
                minn = min(minn, c[tata[j]][j] - f[tata[j]][j]); //calculez capacitatea minima a drumului (capacitate totala-consumata)
            }
            if (minn == 0)
                continue;

            for (j =n+n+1; j>0; j = tata[j]) //modific capacitatile drumurilor + maresc flowul rezidual
            {
                f[tata[j]][j] += minn;
                f[j][tata[j]] -= minn;
            }
            flow=flow+minn;
        }
    }
    fout<<flow<<'\n';
    for (i = 1; i <= n; ++i){
        for (j=0;j<la[i].size();j++)
        {
            if(la[i][j]!=0 && f[i][la[i][j]]!=0) // daca exista muchie intre i si j si daca fluxul ei nu e 0
                fout<<i<<' '<<la[i][j]-n<<'\n';
        }
    }
    return 0;
}


//// V2 -- cu graf rezidual
//
//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <queue>
//
//using namespace std;
//
//ifstream in("harta.in");
//ofstream out("harta.out");
//
//const int dim = 205;
//
//int n, deg_in[2*dim], deg_out[2*dim];
//vector<int> vec[dim];
//int graf_rezidual[2*dim][2*dim];
//queue<int> q;
//int viz[2*dim];
//int tata[2*dim];
//int sursa, destinatie;
//
//int BFS() {
//    for (int i=0; i<=2*n+1; i++) {
//        viz[i] = 0;
//    }
//    viz[sursa] = 1;
//    q.push(sursa);
//    tata[sursa] = -1;
//    while (!q.empty()) {
//        int x = q.front();
//        q.pop();
//        if (x == destinatie) continue;
//        for (auto y:vec[x]) {
//            if (graf_rezidual[x][y] > 0 && !viz[y]) {
//                viz[y] = 1;
//                tata[y] = x;
//                q.push(y);
//            }
//        }
//    }
//    return viz[destinatie];
//}
//
//
//int main() {
//    in >> n;
//    for (int i=1; i<=n; i++) {
//        in >> deg_out[i] >> deg_in[i];
//    }
//    sursa = 0;
//    destinatie = 2*n + 1;
//
//    for (int i=1; i<=n; i++) {
//        vec[sursa].push_back(i);
//        vec[i].push_back(sursa);
//        graf_rezidual[sursa][i] = deg_out[i];
//    }
//
//    for (int i=1; i<=n; i++) {
//        for (int j=1; j<=n; j++) {
//            if (i != j) {
//                vec[i].push_back(n + j);
//                vec[n+j].push_back(i);
//                graf_rezidual[i][n+j] = 1;
//            }
//        }
//    }
//
//    for (int i=1; i<=n; i++) {
//        vec[i+n].push_back(destinatie);
//        vec[destinatie].push_back(i+n);
//        graf_rezidual[i+n][destinatie] = deg_in[i];
//    }
//
//    int maxflow = 0;
//    int mini = INT32_MAX;
//    while (BFS()) {
//        for (auto y:vec[destinatie]) {
//            mini = INT32_MAX;
//            tata[destinatie] = y;
//            for (int j = destinatie; j != sursa; j = tata[j]) {
//                mini = min(mini, graf_rezidual[tata[j]][j]);
//            }
//
//            maxflow += mini;
//
//            for (int j = destinatie; j != sursa; j = tata[j]) {
//                graf_rezidual[tata[j]][j] -= mini;
//                graf_rezidual[j][tata[j]] += mini;
//            }
//        }
//    }
//
//    out << maxflow << "\n";
//    for (int i=1; i<=n; i++) {
//        for (int j=1; j<=n; j++) {
//            if (i != j && graf_rezidual[i][n+j] == 0) {
//                out << i << " " << j << "\n";
//            }
//        }
//    }
//    return 0;
//}