Cod sursa(job #2875606)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 21 martie 2022 23:35:00
Problema Flux maxim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;

using Matrix2D = vector<vector<int>>;

int dfs(int node, const int& DEST, int minDelta, vector<bool>& vis,
        Matrix2D& g, Matrix2D& c, Matrix2D& f){
    if(vis[node]){
        return 0;
    }
    vis[node] = true;
    
    if(node == DEST){
        return minDelta;
    }

    for(int nextNode: g[node]){
        int delta = c[node][nextNode] - f[node][nextNode];
        if(delta > 0){
            int flow = dfs(nextNode, DEST, min(minDelta, delta), vis, g, c, f);
            if(flow > 0){
                f[node][nextNode] += flow;
                f[nextNode][node] -= flow;
                return flow;
            }
        }
    }

    return 0;
}

int computeMaxFlow(Matrix2D& g, Matrix2D& c, const int& SRC, const int& DEST){
    const int N = g.size();

    Matrix2D f(N, vector<int>(N));
    vector<bool> vis(N);

    int maxFlow = 0;
    while(true){
        fill(vis.begin(), vis.end(), false);
        int delta = dfs(SRC, DEST, INT_MAX, vis, g, c, f);
        if(delta > 0){
            maxFlow += delta;
        }else{
            break;
        }
    }

    return maxFlow;
}

int main(){
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");

    int N, M;
    cin >> N >> M;

    Matrix2D g(N);
    Matrix2D c(N, vector<int>(N));

    int x, y;
    for(int i = 1; i <= M; ++i){
        cin >> x >> y;
        --x;
        --y;
        cin >> c[x][y];
        g[x].push_back(y);
        g[y].push_back(x);
    }

    cout << computeMaxFlow(g, c, 0, N - 1);

    cin.close();
    cout.close();
    return 0;
}