Cod sursa(job #2969358)

Utilizator PopelEmilBogdanPopel Emil-Bogdan PopelEmilBogdan Data 22 ianuarie 2023 21:41:21
Problema Flux maxim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <bits/stdc++.h>
#include <limits>
using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int capacity[1001][1001], n, m, flow, flowMax;
vector<int> viz(1001, 0);
vector<bool> parents(1001, false);
vector<vector<int>> graph;

bool bfs()
{
    parints.assign(n + 1, 0);
    visited.assign(n + 1, false);
    viz[1] = true;
    queue<int> coada;
    coada.push(1);
    while (!coada.empty())
    {
        int currentNode = coada.front();
        coada.pop();


        for (auto &neigbour : graph[currentNode])
        {
            if (viz[neigbour] || capacity[currentNode][neigbour] <= 0)
            {
                continue;
            }
            coada.push(neigbour);
            viz[neigbour] = true;
            parents[neigbour] = currentNode;
            if( neigbour == n)
            {
                return true;
            }

        }
    }
    return false;
}

int main()
{
    int node1, node2, cap;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> node1 >> node2 >> cap;
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
        capacity[node1][node2] = cap;
    }

    while (bfs())
    {
        for (auto &neigh : graph[n])
        {
            if (!viz[neigh])
            {
                continue;
            }
            flow = numeric_limits<int>::max();
            parents[n] = neigh;
            int aux = n;

            while(aux != 1)
            {
                flow = min(capacity[parents[aux]][aux], flow);
                aux = parents[aux];
            }
            if(!flow) continue;
            aux = n;

            while(aux != 1)
            {
                capacity[parents[aux]][aux] -= flow;
                capacity[parents[aux]][aux] += flow;
                aux = parents[aux];
            }
            flowMax += flow;
        }
        fout << flowMax;
        return 0;
    }
}
/***
Parcurgem graful din nodul radacina trecand prin muchii cu flux != 0. drumul e reconstruit folosind vectorii de noduri vizitate si de parinti.
Cu fiecare parcurgere se scade flow ul minim din toate muchiile drumului si se updateaza flow ul maxim.
*/