Cod sursa(job #2834521)

Utilizator Andreea__Zavoiu Andreea Andreea__ Data 17 ianuarie 2022 10:22:01
Problema Flux maxim Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <queue>
#define Nmax 1005
#define inf 1<<30
using namespace std;

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

int viz[Nmax], cap[Nmax][Nmax], flux[Nmax][Nmax], tata[Nmax]; // p = tata
int n, m, flux_max;
vector<int> la[Nmax];
queue<int> q;

bool bfs(int s, int d)
{
    memset(viz, 0, sizeof viz); // make all vertices not visited

    q.push(s);
    while(!q.empty())
    {
        int poz = q.front();
        q.pop();

        if(poz == d)    // s-a terminat arborele BFS => pot iesi din subprogram
            return 1;

        for(auto vecin : la[poz])
        {
            if(cap[poz][vecin] > flux[poz][vecin] && !viz[vecin]) // fiecare muchie de pe drum sa mai poata adauga flux (sa nu fie saturata)
            {
                tata[vecin] = poz;
                viz[vecin] = 1;
                q.push(vecin);
            }
        }
    }
    return 0;
}

int main()
{
    int a, b, c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++) // indexare muchii de la 1
    {
        fin >> a >> b >> c;
        cap[a][b] = c;      // capacitatea muchiei de la a la b => de la b la a va fi -cap[a][b]
        la[a].push_back(b);
        la[b].push_back(a); // trb luate si muchiile inverse
    }

    while(bfs(1, n)) // cat timp gasesc un drum de ameliorare de la sursa la destinatie
    {
        for(int vecin : la[n])
        {
            if(flux[vecin][n] == cap[vecin][n]) continue;// nu e muchie valida deci continua cautarea
            
            if (!viz[vecin]) continue;

            tata[n] = vecin;
            int min_flux = inf; // infinit

            // parcurg drumul de la d la s pentru a determina cu cat se poate modifica fluxul pe acel drum
            for(int x = n; x != 1; x = tata[x])
                min_flux = min(min_flux, cap[tata[x]][x] - flux[tata[x]][x]);

            if(min_flux == 0)
                continue;

            // update residual capacities of the edges and reverse edges along the path
            for(int x = n; x != 1; x = tata[x])
            {
                flux[tata[x]][x] += min_flux;
                flux[x][tata[x]] -= min_flux;
            }
            flux_max += min_flux;
        }
    }

    fout << flux_max;
    return 0;
}