Cod sursa(job #2875597)

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

int dfs(int node, const int& DEST, int minDelta,
        vector<vector<int>>& g, 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: g[node]){
        for(pair<int, int> xy: vector<pair<int, int>>{{node, nextNode}, {nextNode, node}}){
            int x = xy.first;
            int y = xy.second;
            int delta = c[x][y] - f[x][y];
            if(delta > 0){
                int flow = dfs(y, DEST, min(minDelta, delta), g, c, f, vis, N);
                if(flow > 0){
                    f[x][y] += flow;
                    f[y][x] -= flow;
                    return flow;
                }
            }
        }
    }
    return 0;
}

int computeMaxFlow(vector<vector<int>>& g,
                   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, g, 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>> g(N + 1);
    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];
        g[x].push_back(y);
        g[y].push_back(x);
    }

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

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