max_flow.cpp

#include <vector>
#include <iostream>

using namespace std;

#define MAX_V 50
#define INF (1<<20)

#include <vector>

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


using namespace std;


vector<edge> G[MAX_V];
bool used[MAX_V];


void add_edge(int from, int to, int cap)
{
    G[from].push_back((edge){to, cap, (int)G[to].size()});
    G[to].push_back((edge){from, 0, (int)G[from].size()-1});
    
}


int dfs(int v, int t, int f) 
{
    cout << "v: " << v << " t: " << t << " f: " << f << endl;
    if (v == t) {
        return f;
    }
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (!used[e.to] && e.cap > 0) {
            int d = dfs(e.to, t, min(f, e.cap));
            cout << "d: " << d << endl;
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;

                int t = G[v][i].to;
                int rev = G[v][i].rev;
                int cap = G[v][i].cap;
                cout << "from: " << v << " to: " << t << " cap: " << cap << " rev: " << rev << endl;


                int t1 = G[e.to][e.rev].to;
                int cap1 = G[e.to][e.rev].cap;
                int rev1 = G[e.to][e.rev].rev;
                
                cout << "from1: " << e.to << " to1: " << t1 << " cap1: " << cap1 << " rev1: " << rev1 << endl;
                cout << "------------------------------------" << endl;
                return d;
            }
        }
    }
    return 0;
}


int max_flow(int s, int t)
{
    int flow = 0;
    for (;;) {
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, INF);
        if (f == 0) {
            return flow;
        }
        flow += f;
    }
}


int main()
{
    vector<vector<int> > to =
    {
        {1,3},
        {2,4},
        {3,4},
        {4}
    };

    vector<vector<int> > cap =
    {
        {10,2},
        {6,6},
        {3,8},
        {5}
    };

    for (int i=0; i < to.size(); i++) {
        for (int j=0; j < to[i].size(); j++) {
            cout << "from: " << i << " to: " << to[i][j] << " cap: " << cap[i][j] << endl;
            add_edge(i, to[i][j], cap[i][j]);
        }
    }

for (int i=0; i < 5; i++) {
    for (int j=0; j < G[i].size(); j++) {
        int t = G[i][j].to;
        int rev = G[i][j].rev;
        int cap = G[i][j].cap;
        cout << "from: " << i << " to: " << t << " cap: " << cap << " rev: " << rev<< endl;
    }
}

    cout << "result:" << endl;
    cout << max_flow(0,4) << endl;
}