template/coldwater/dinic

#define MAXN (3010)
#define INF (0x3f3f3f3f)

struct Dinic{
	struct Edge{
		int from, to, cap, flow;
	};
	int n, m, s, t;
	std::vector<Edge> edges;
	std::vector<int> G[MAXN];
	bool vis[MAXN];
	int d[MAXN], cur[MAXN];
	
	void addedge(int from, int to, int cap){
		edges.push_back({from, to, cap, 0});
		edges.push_back({to, from, 0, 0});
		m = edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}
	
	bool bfs(){
		memset(vis, 0, sizeof(vis));
		std::queue<int> queue;
		queue.push(s);
		d[s] = 0;
		vis[s] = 1;
		while(!queue.empty()){
			int u = queue.front(); queue.pop();
			for(auto i : G[u]){
				Edge &e = edges[i];
				if(!vis[e.to] && e.cap > e.flow){
					vis[e.to] = 1;
					d[e.to] = d[u] + 1;
					queue.push(e.to);
				}
			}
		}
		return vis[t];
	}
	
	int dfs(int u, int now){
		if(u == t || !now) return now;
		int flow = 0, f;
		
		for(int &i = cur[u]; i < G[u].size(); ++ i){
			Edge &e = edges[G[u][i]];
			if(d[u] + 1 == d[e.to] && (f = dfs(e.to, std::min(now, e.cap - e.flow))) > 0){
				e.flow += f;
				edges[G[u][i] ^ 1].flow -= f;
				flow += f;
				now -= f;
				if(!now) break;
			}
		}
		return flow;
	}
	
	int maxflow(int s, int t){
		this -> s = s; this -> t = t;
		int flow = 0;
		while(bfs()){
			memset(cur, 0, sizeof(cur));
			flow += dfs(s, INF);
			if(flow >= INF) return INF;
		}
		return flow;
	}
	
	void clear(){
		for(int i = 0; i < MAXN; ++ i) G[i].clear();
		edges.clear();
	}
}dinic;