Cod sursa(job #2961278)

Utilizator antonia2003antonia oancea antonia2003 Data 6 ianuarie 2023 02:57:23
Problema Taramul Nicaieri Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector<vector<int> > la;
vector<int> tata;

int n, dest, x,y, cap[201][201], maxim=999999;
int cmax = 0;


//BFS clasic
bool BFS()
{
    vector<int> viz(2 * n + 1);
    queue<int> q;
    q.push(0);
    viz[0] = 1;
    tata[0] = -1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        //for(auto v: la[u])
        for(int i=0;i<la[u].size();i++)
        {
            int v=la[u][i];
            if(viz[v]==0 && cap[u][v]!=0)
            {
                tata[v] = u;
                if(v == dest)
                    return true;
                viz[v] = 1;
                q.push(v);
            }
        }
    }
    return false;
}

int Edmonds_Karp()
{

    while(BFS())
    {
        int aux, next=dest, path_flow = maxim;
        while(next != 0)
        {
            aux = tata[next];
            path_flow=min(cap[aux][next],path_flow);
            next = tata[next];
        }
        next=dest;
        while(next != 0)
        {
            aux = tata[next];
            cap[aux][next] -= path_flow;
            cap[next][aux] += path_flow;
            next = tata[next];
        }
        cmax = cmax + path_flow;
    }
    return cmax;
}


int main()
{
    //citim nr de muchii
    f >> n;
    dest= 2 * n + 1;
    la.resize(201);
    tata.resize(2 * n + 1);

    // cream un graf complet de n noduri cu ajutorul caruia avem in stanga nodurile propriu zise si in dreapta copiile lor
    // adaugam capacitatea 1 pe muchia dintre ele
    for(int i=1; i <= n; i++)
        for(int j= 1 + n; j <= 2 * n; j++)
        {
            if(i!= j - n)
            {
                la[i].push_back(j);
                la[j].push_back(i);
                cap[i][j]=1;
            }
        }

    // legam nodurile de un nod fictiv 0 pentru gradul intern - capacitatea e gradul intern
    //legam o copie a nodurilor de un nod fictiv 2*n+1 pentru gradul extern - capacitatea e gradul extern
    for(int i=1; i <= n; i++)
    {
        f >> x >> y;
        la[0].push_back(i);
        la[i].push_back(0);
        la[dest].push_back(i + n);
        la[i + n].push_back(dest);
        cap[0][i]=x;
        cap[i + n][dest]=y;
    }


    g<<Edmonds_Karp()<<endl;

    //afisam perechiile de noduri care au muchii intre ele
    for(int i=1; i <= n; i++)
        for(int j= 1 + n; j <= 2 * n; j++)
        {
            if(cap[j][i])
                g << i << " " << j - n << "\n";
        }
    return 0;
}