Min Cost Max Flow

#include<bits/stdc++.h>
#define ll long long

// Note:
//      0 or 1-indexed are both supported
//      Solve the problem of min cost max flow (or min cost K flow)
//      To solve for min cost max flow, set K = big number (oo)
struct MCMF {
    
    struct Edge {
        int to, cost, cap, flow, backEdge;
    };
    
    int n;
    vector<Edge> *g; // graph
    int inf;
  
    MCMF(){}
  
    void init(int n_) {
        n = n_;

        g = new vector<Edge> [n+1];
        
        inf = 2e9+9;
    }
  
    void addEdge(int u, int v, int cap, int cost) {
        
        Edge e1 = { v, cost,  cap, 0, g[v].size() };
        Edge e2 = { u, -cost, 0,   0, g[u].size() };

        g[u].push_back(e1); 
        g[v].push_back(e2);
        
    }
    
    pair<int, int> minCostMaxFlow(int s, int t, int K) {
        
        int flow = 0, cost = 0;
        vector<int> state(n+1), from(n+1), from_edge(n+1), d(n+1);
        deque<int> q;
        
        while (flow < K) {
            
            // re-init values
            fill(state.begin(), state.end(), 0);
            fill(d.begin(),     d.end(),     inf);
            fill(from.begin(),  from.end(), -1);

            state[s] = 1; 
            d[s] = 0;
            q.clear(); 
            q.push_back(s); 
            
            // find the shortest path in residual graph (algo: SPFA)
            while(!q.empty()) {
                
                int v = q.front(); 
                q.pop_front(); 
                state[v] = 0;
                
                for (int i = 0; i < g[v].size(); i++) {
                    
                    Edge &e = g[v][i];
                    
                    if (e.flow >= e.cap || d[e.to] <= d[v] + e.cost)
                        continue;
                        
                    int to = e.to; 
                    d[to] = d[v] + e.cost;
                    from[to] = v; 
                    from_edge[to] = i;
                    
                    if (!state[to]) {
                        q.push_back(to);
                        state[to] = 1;
                    }
                    
                }
                
            }
        

            if (d[t] == inf) break;
            
            // find how much can we flow through this pipe.
            int it = t, addflow = K - flow;
            while (it != s) {
                addflow = min(addflow,
                        g[from[it]][from_edge[it]].cap
                        - g[from[it]][from_edge[it]].flow);
                it = from[it];
            }
            
            // flow through this line. Adjust flow of edges.
            it = t;
            while (it != s) {
                g[from[it]][from_edge[it]].flow += addflow;
                g[it][g[from[it]][from_edge[it]].backEdge].flow -= addflow;
                cost += g[from[it]][from_edge[it]].cost * addflow;
                it = from[it];
            }
            
            flow += addflow;
            
        }
        
        return {cost,flow};
    }
};