Cod sursa(job #2961328)

Utilizator elenaa_g23Elena Georgescu elenaa_g23 Data 6 ianuarie 2023 10:55:09
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>

using namespace std;

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

int N,M;
int capacitate[1001][1001];
vector<vector<int>> adj;
int element, nod, flux_maxim, flux_minim, firstelem;
vector<int> tata;
vector<bool> vizitat;
queue<int> coada;

#define M 2*N+1


int creare_lant()
{

    while(!coada.empty()) coada.pop();

    tata.clear();
    tata.resize(M+1,0);
    vizitat.clear();
    vizitat.resize(M+1,false);

    coada.push(0);
    vizitat[0]=true;

    while(!coada.empty())
        {
        firstelem=coada.front();
        coada.pop();


        for(auto p:adj[firstelem])
        {
            if(vizitat[p]==false && capacitate[firstelem][p]>0)
            {
                coada.push(p);
                vizitat[p]=true;
                tata[p]=firstelem;
                if(p==M) return 1;
            }
        }

    }
        return 0;

}

void calcul_flux()
{
    for(auto p:adj[N])
        if(vizitat[p]==true)

    {
        element = M;
        flux_minim=INT_MAX;

        while (element!=0) // caut care este fluxul minim cu care poate fi modificat lantul curent
        {
            nod = tata[element];
            if(flux_minim > capacitate[nod][element])
                    flux_minim = capacitate[nod][element];

            element = nod;

        }

        element = M;

        while (element!=0) // dupa ce am aflat fluxul minim, actualizez fluxurile
        {
            nod = tata[element];
            capacitate[nod][element] -= flux_minim;
            capacitate[element][nod] += flux_minim;
            element = nod;

        }

        flux_maxim = flux_maxim + flux_minim;

    }
}



int main()
{
    f>>N;

    adj.resize(M+1);

    int grad1, grad2;

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

        adj[0].push_back(i);
        adj[i].push_back(0);
        adj[N+i].push_back(M);
        adj[M].push_back(N+1);

        f>>grad1>>grad2;
        capacitate[0][i]=grad1;
        capacitate[N+i][M]=grad2;

        for(int j=N+1;j<=M-1;j++) // cream legaturi intre toate nodurile si duplicatele
        {
            if(j-i!=N) // cu exceptia legaturii dintre nodului curent si duplicatul sau
            {
                adj[i].push_back(j);
                adj[j].push_back(i);
                capacitate[i][j]=1;
            }
        }
    }

    flux_maxim=0;


    while (creare_lant())
    {
        calcul_flux();
    }

    g<<flux_maxim<<'\n';

    for(int i=1;i<=N;i++)
    {
     for(int j=N+1;j<=M;j++)
          if (capacitate[j][i]==1)
        {
        g<<i<<' '<< j-N<< '\n';
        }
    }

}