Cod sursa(job #2964480)

Utilizator culiteramicacristiana culiteramica Data 13 ianuarie 2023 08:00:53
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");


///ca la flux doar ca un nod de acolo este inlocuit cu x noduri unde x este capacitatea dinspre nodul respectiv si sursa/destinatie.

vector<vector<int>> GRAF;
int capacitate[201][201], s, t,n, a, b;
vector<int> tata;

bool bfs(){
    //BFS pentru a verifica fluxul maxim
    vector<bool> viz(t);
    queue<int> c;

    c.push(s);
    viz[s]=true;
    tata[s]=-1;

    while(!c.empty())
    {
        int nod_curent=c.front();
        c.pop();
        for(auto vec :GRAF[nod_curent])
        {
            if(!viz[vec] && capacitate[nod_curent][vec])
            {
                tata[vec]=nod_curent;
                if(vec==t)
                    return true;
                viz[vec]=true;
                c.push(vec);
            }
        }
    }
    return false;
}

int EK(){
    long fm = 0;
    while(bfs()==true)
    {
        int u;
        int v=t;
        int flux = INT_MAX;
        while(v!=s)
        {
            u=tata[v];
            if(capacitate[u][v]<flux)
                flux=capacitate[u][v];
            v=tata[v];
        }
        v=t;
        while(v!=s){
            u=tata[v];
            capacitate[v][u]+=flux;
            capacitate[u][v]-=flux;
            v=tata[v];
        }

        fm+=flux;
    }
    return fm;

}

int main() {

    fin>>n;
    s = 0;
    t = 2*n+1;
    GRAF.resize(201);
    tata.resize(2*n+1);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                GRAF[i].push_back(j+n);
                GRAF[j+n].push_back(i);
                capacitate[i][j+n]=1;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;  ///a drumuri pleaca din i, b drumuri intra in i

        GRAF[s].push_back(i);
        GRAF[i].push_back(s);
        capacitate[s][i] = a;

        GRAF[t].push_back(i+n);
        GRAF[i+n].push_back(t);
        capacitate[i+n][t]=b;
    }

    fout<<EK()<<endl;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(capacitate[j+n][i]==1)
                fout<<i<<" "<<j<<endl;
        }
    }

    return 0;
}