# 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) {
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) {
it = from[it];
}

}

return {cost,flow};
}
};```