Cod sursa(job #3193517)

Utilizator modreanumModreanu Maria modreanum Data 14 ianuarie 2024 19:10:33
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <array>
#include <climits>
using namespace std;

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


vector<int>parinte(203);
array<vector<int>,203>G;
int n,graf_rezidual[203][203],grad_in[203],grad_out[203];

int BFS(vector<int>& parinte)
{
    queue<int> Q;
    int i,nod,s=0,t=2*n+1;

    for(i=1;i<2*n+2;i++)
        parinte[i]=-1;//se seteaza toate nodurile nevizitate

    Q.push(s);
    parinte[s]=0;//parintele sursei e setat ca vizitat
//daca nu am vizitat nodul il adaugam si il setam ca vizitat pana cand se ajunge in t
    while(Q.size()>0)
    {
        nod=Q.front();
        Q.pop();
        for(auto i:G[nod])
            if(graf_rezidual[nod][i]&&parinte[i]==-1)
            {
                parinte[i]=nod;
                if(t!=i)
                    Q.push(i);
                else
                    return 1;
            }
    }
    return 0;
}


int main()
{

    int i,s=0,j,t,flux_maxim=0,nod,nod2,flux=INT_MAX;
//citesc datele
//s si t sunt 0 si n*2+!
    fin >> n;
    t=2*n+1;
    for (i=1;i<n+1;i++)
        fin>>grad_out[i]>>grad_in[i];
//adaug in graf muchii de la sursa la primul set si de la al doilea set la t pentru BFS
//in graful rezidual setez capacitatile egale cu cate drumuri ies sau intra in oras
    for(i=1;i<n+1;i++)
    {
        G[i].push_back(s);
        G[s].push_back(i);
        G[n+i].push_back(t);
        G[t].push_back(n+i);
        graf_rezidual[s][i]=grad_out[i];
        graf_rezidual[n+i][t]=grad_in[i];
    }
//intre primul si al doilea set de orase setez capacitatea 1 pentru ca poate exista maxim 1 drum intre 2 orase daca acestea nu sunt identice
    for(i=1;i<n+1;i++)
        for(j=n+1;j<2*n+1;j++)
            if(j==n+i)
                graf_rezidual[i][j]=0;
            else
            {
                G[i].push_back(j);
                G[j].push_back(i);
                graf_rezidual[i][j]=1;
            }
//cat timp gasesc drumuri gasesc fluxul maxim posibil pe acel drum, updatez graful rezidual de la t la s si suma fluxurilor
    while(BFS(parinte)==1)
    {
        nod=t;
        while(nod!=s)
        {
            nod2=parinte[nod];
            if (flux>graf_rezidual[nod2][nod])
                flux=graf_rezidual[nod2][nod];
            nod=nod2;
        }
        nod=t;
        while(nod!=s)
        {
            nod2=parinte[nod];
            graf_rezidual[nod][nod2]=graf_rezidual[nod][nod2]+flux;
            graf_rezidual[nod2][nod]=graf_rezidual[nod2][nod]-flux;
            nod=nod2;
        }
        flux_maxim=flux_maxim+flux;
    }

    fout<<flux_maxim<<"\n";

    //daca orasele nu sunt identice si capacitatea pe graful rezidual e 0 inseamna ca exista un drum intre orase si le afisez
    for(i=1;i<=n;i++)
    {
        for(j=n+1;j<2*n+1;j++)
            if (graf_rezidual[i][j]==0)
                fout<<i<<" "<<j-n<<"\n";
    }

    return 0;
}