# Dinic Algorithm (1)

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

// Dinic to find max-flow/min-cut
// Usage:
//      Dinic dinic;
//      dinic.init(n);
//      maxFlow = dinic.run(source, sink);
struct Dinic {
int n;
vector< vector<ll> > capa;
vector< vector<ll> > flow;
vector<int> dlevel;
vector<int> prev;
vector<int> visit;

int maxCapacity;

Dinic(){
maxCapacity = 1e9;
}

void init(int n_) {
n = n_;

capa.resize(n+1);
flow.resize(n+1);
dlevel.resize(n+1);
prev.resize(n+1, 0);
visit.resize(n+1);

for (int i = 0; i <= n; ++i) {
capa[i].resize(n+1);
flow[i].resize(n+1);
fill(capa[i].begin(), capa[i].begin()+n+1, 0);
fill(flow[i].begin(), flow[i].begin()+n+1, 0);
}

fill(dlevel.begin(), dlevel.begin()+n+1, 0);
fill(prev.begin(), prev.begin()+n+1, 0);
fill(visit.begin(), visit.begin()+n+1, 0);
}

void addEdge(int u, int v, int w) {
capa[u][v] += w;
capa[v][u] += w;
flow[v][u] += w;
}

for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
if (i != j && capa[i][j] > 0)
}

bool constructLevel(int source, int sink) {
fill(dlevel.begin(), dlevel.begin()+n+1, -1);
dlevel[source] = 0;

queue<int> que;
que.push(source);

while(!que.empty()) {
int vertex = que.front();
que.pop();

for (int i = 0; i < adj[vertex].size(); ++i) {
if (dlevel[next] >= 0)
continue;

if (capa[vertex][next] > flow[vertex][next]) {
que.push(next);
dlevel[next] = dlevel[vertex] + 1;
}

}
}

return dlevel[sink] >= 0;
}

ll makeFlow(int source, int sink) {

ll ret = 0;

fill(visit.begin(), visit.begin()+n+1, 0);

stack<int> stk;
stk.push(source);

while(!stk.empty()) {

int now = stk.top();

if (now != sink) {

for (int i = 0; i < adj[now].size() && stk.top() == now; ++i) {

if (dlevel[next] != dlevel[now] + 1 || visit[next])
continue;

if (capa[now][next] > flow[now][next]) {
stk.push(next);
prev[next] = now;
}
}

if (stk.top() == now) {
stk.pop();
visit[now] = 1;
}

}
else { // now == sink
ll f = maxCapacity, bottleneck;

for (int cur = sink; cur != source; cur = abs(prev[cur])) {
f = min(f, capa[prev[cur]][cur] - flow[prev[cur]][cur]);
}

for (int cur = sink; cur != source; cur = abs(prev[cur])) {

flow[prev[cur]][cur] += f;
flow[cur][prev[cur]] -= f;

if (capa[prev[cur]][cur] == flow[prev[cur]][cur])
bottleneck = prev[cur];
}

ret += f;

while(!stk.empty() && stk.top() != bottleneck)
stk.pop();
}

}

//      cout << "ret: " << ret << endl;
return ret;
}

ll run(int source, int sink) {