Takefumi Yamamura's blog

This blog is for my memorandum about programming and English.

Happy Coding

This blog is for my memorandum

Network Flow - Maximum Flow

problem

Maximum Flow | Aizu Online Judge

code

#include <iostream>
#include <vector>

#define INF (1<<15)

using namespace std;

struct edge{
    int to;
    int cap;
    int rev_id;
};

class FordFulkerson
{
private:
    vector<vector<edge> > adj;
    int v;
    int e;
    vector<bool> visited;
public:
    FordFulkerson() {
        cin >> v;
        cin >> e;
        adj.resize(v);
        for (int i = 0; i < e; ++i)
        {
            int u;
            int v;
            int c;
            cin >> u >> v >> c;
            adj[u].push_back((edge){v, c, adj[v].size()});
            adj[v].push_back((edge){u, 0, adj[u].size() - 1});
        }
    }


    int dfs(int from, int goal, int flow) {
        if(from == goal) return flow;
        visited[from] = true;
        for (int i = 0; i < adj[from].size(); ++i)
        {
            edge &e = adj[from][i];
            if(!visited[e.to] && e.cap > 0) {
                int d = dfs(e.to, goal, min(e.cap, flow));
                if(d > 0) {
                    adj[from][i].cap -= d;
                    adj[e.to][e.rev_id].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    void exec() {
        int flow_sum = 0;
        while(true) {
            visited = vector<bool>(v, false);
            int flow = dfs(0, v - 1, INF);
            if(flow == 0) {
                cout << flow_sum << endl;
                return;
            }
            flow_sum += flow;
        }
    }
};

int main() {
    FordFulkerson ff = FordFulkerson();
    ff.exec();
}