Cod sursa(job #2875817)

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

class Graph{
public:
    const int N;
    vector<vector<int>> neighbors;
    vector<vector<int>> capacity;

public:
    Graph(const int& N): N(N){
        neighbors.resize(N);
        capacity.assign(N, vector<int>(N));
    }

    void addEdge(int x, int y, int c){
        neighbors[x].push_back(y);
        neighbors[y].push_back(x);
        capacity[x][y] = c;
    }
};

class FordFulkerson{
private:
    const Graph& G;
    const int N;
    const int SRC;
    const int DEST;
    vector<vector<int>> f;
    vector<bool> vis;

    int dfs(int node, int minDelta){
        if(vis[node]){
            return 0;
        }
        
        vis[node] = true;
        
        if(node == DEST){
            return minDelta;
        }

        for(int nextNode: G.neighbors[node]){
            int delta = G.capacity[node][nextNode] - f[node][nextNode];
            if(delta > 0){
                int flow = dfs(nextNode, min(minDelta, delta));
                if(flow > 0){
                    f[node][nextNode] += flow;
                    f[nextNode][node] -= flow;
                    return flow;
                }
            }
        }

        return 0;
    }

public:
    FordFulkerson(const Graph& G, const int& SRC, const int& DEST):
                  G(G), N(G.N), SRC(SRC), DEST(DEST){
        f.assign(N, vector<int>(N));
        vis.resize(N);
    }

    int computeMaxFlow(){
        int maxFlow = 0;
        while(true){
            fill(vis.begin(), vis.end(), false);
            int delta = dfs(SRC, INT_MAX);
            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;

    Graph G(N);
    int x, y, c;
    for(int i = 0; i < M; ++i){
        cin >> x >> y >> c;
        G.addEdge(x - 1, y - 1, c);
    }

    cout << FordFulkerson(G, 0, N - 1).computeMaxFlow();

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