Cod sursa(job #2960532)

Utilizator Nicolae11Mihaila Nicolae Nicolae11 Data 4 ianuarie 2023 16:42:42
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.07 kb
/*
    Ideea de rezolvare a algoritmului este urmatoarea:
    Folosim algoritmul de Max Flow. In plus, folosim optimizarea mentionata pe infoarena: La fiecare pas construim arborele BFS (excluzand destinatia),
si acum un drum de la sursa la destinatie e reprezentat de un drum de la sursa (care este radacina arborelui) la o frunza legata de destinatie printr-o
muchie nesaturata. Astfel putem la un pas sa marim fluxul pe un numar maximal de astfel de drumuri, fara a mai reface BFS-ul. Aceasta optimizare
reduce destul de mult timpul de executie.
    Aici vine partea specifica problemei. Acestia sunt pasii rezolvarii:
    Cream o dublura pentru fiecare nod.
    Conectam toate nodurile la dubluri, mai putin la propria dublura, printr-o muchie de capacitate 1.
    Adaugam nodul sursa si nodul destinatie.
    Conectam sursa la toate nodurile originale prin muchii cu capacitatea egala cu gradul extern al nodurilor.
    Conectam toate dublurile la destinatie prin muchii cu capacitatea egala cu gradul intern al nodurilor originale.
    Aplicam MaxFlow
    Muchiile saturate (cele care au capacitate 1 in graf si capacitate 0 in graful rezidual) dintre noduri si dubluri sunt muchiile grafului orientat

Complexitate:
Fie n = numarul de noduri, m = numarul de muchii
Timp: O(n*m^2) ///totusi, avem optimizarea cu arborele BFS
Memorie: O(n^2) ///matrice de adiacenta
*/
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,m,s,t;
int viz[205];
int parinte[205];
int graf[205][205];
int graf_rez[205][205];
long long flux_maxim;
void AddMuchie(int x, int y, int c)
{
    graf_rez[x][y]=graf[x][y]=c;
}
bool bfs()
{
    memset(viz,0,sizeof(viz));
    memset(parinte,0,sizeof(parinte));
    queue <int> q;
    viz[s]=1;
    q.push(s);
    parinte[s]=-1;
    while(!q.empty())
    {
        int act=q.front();
        q.pop();
        if(act==t) ///am ajuns la nodul t, deci exista un drum de la s la t pe care nu l-am saturat
            return true;
        for(int i=0;i<=2*n+1;i++) ///ne uitam prin vecinii nodului actual
            if(viz[i]==0 && graf_rez[act][i]>0) ///nodul nu e vizitat, iar muchia (fie ea din graful rezidual sau nu) mai accepta flux
            {
                viz[i]=1;
                parinte[i]=act;
                q.push(i);
            }
    }
    return false;
}
int maxFlow()
{
    while(bfs()) ///cat timp mai exista drumuri nesaturate de la s la t
    {
        for(int i=0;i<=2*n;i++)
        {   if(viz[i]!=0 && graf_rez[i][t]>0)
            {
                int aux_flux=1<<30; ///facem asta ca sa luam minimul de pe drum
                parinte[t]=i;
                int j=t;
                while(parinte[j]!=-1) ///calatorim din tata in tata pana ajungem la s si vedem cat flux putem baga pe drumul ala (bottleneck inclus)
                {
                    aux_flux=min(aux_flux,graf_rez[parinte[j]][j]);
                    j=parinte[j];
                }
                if(aux_flux!=0) ///Putem adauga flux pe drum
                {
                    int j=t;
                    while(parinte[j]!=-1) ///mergem din tata in tata si modificam muchiile pe graful normal + cel rezidual
                    {
                        graf_rez[parinte[j]][j]-=aux_flux;
                        graf_rez[j][parinte[j]]+=aux_flux;
                        j=parinte[j];
                    }
                    flux_maxim=flux_maxim+aux_flux; ///adaugam la flux_maxim fluxul pe care il avem pe drumul calculat
                }
            }
        }
    }
    return flux_maxim;
}
int main()
{
    f>>n;
    s=0;
    t=2*n+1;
    int x,y;
    for(int i=1;i<=n;i++)
    {
        f>>x>>y;
        AddMuchie(s,i,x);
        AddMuchie(n+i,t,y);
    }
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(i!=j-n)
                AddMuchie(i,j,1);
    g<<maxFlow()<<'\n';
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(graf[i][j]==1 && graf_rez[i][j]==0)
                g<<i<<' '<<j-n<<'\n';
    return 0;
}