Cod sursa(job #2875595)

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

int dfs(int node, const int& DEST, int minDelta,
        vector<vector<int>>& c, vector<vector<int>>& f,
        vector<bool>& vis, const int& N){
    if(vis[node]){
        return 0;
    }
    vis[node] = true;
    if(node == DEST){
        return minDelta;
    }
    for(int nextNode = 1; nextNode <= N; ++nextNode){
        int delta = c[node][nextNode] - f[node][nextNode];
        if(delta > 0){
            int flow = dfs(nextNode, DEST, min(minDelta, delta), c, f, vis, N);
            if(flow > 0){
                f[node][nextNode] += flow;
                f[nextNode][node] -= flow;
                return flow;
            }
        }
    }
    return 0;
}

int computeMaxFlow(vector<vector<int>>& c, const int& N,
                   const int& SRC, const int& DEST){
    vector<vector<int>> f(N + 1, vector<int>(N + 1));
    vector<bool> vis(N + 1);
    int maxFlow = 0;
    while(true){
        fill(vis.begin(), vis.end(), false);
        int delta = dfs(SRC, DEST, INT_MAX, c, f, vis, N);
        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;

    vector<vector<int>> c(N + 1, vector<int>(N + 1));

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

    cout << computeMaxFlow(c, N, 1, N);

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