Dinic Flow

/**
maxflow YouKnowWho 's template ...  https://codeforces.com/contest/498/submission/45850199
(i)
/// konig's theorem :
In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.
https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)
problem: https://codeforces.com/gym/104945/problem/B
/**/

struct edge{
	int to, rev, flow, w;
};

struct dinic
{
	int d[N], done[N], s, t;
	vector<edge> g[N];
	/// N equals to node_number

	void addedge(int u, int v, int w)
	{
		edge a={v,(int)g[v].size(),0,w};
		edge b={u,(int)g[u].size(),0,0};

		/// If the graph has bidirectional edges
		/// Capacity for the edge b will equal to w
		/// For directed, it is 0

		g[u].emplace_back(a);
		g[v].emplace_back(b);
	}

	bool bfs()
	{
		memset(d,-1,sizeof(d));
		d[s]=0;
		queue<int>q;
		q.push(s);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(auto &e: g[u])
			{
				int v=e.to;
				if(d[v]==-1 && e.flow<e.w)
				{
					d[v]=d[u]+1;
					q.push(v);
				}
			}
		}
		return d[t]!=-1;
	}

	int dfs(int u, int flow)
	{
		if(u==t) return flow;
		for(int &i=done[u]; i<(int)g[u].size(); i++)
		{
			edge &e=g[u][i];
			if(e.w<=e.flow) continue;
			int v=e.to;
			if(d[v]==d[u]+1)
			{
				int nw=dfs(v,min(flow,e.w-e.flow));
				if(nw>0)
				{
					e.flow+=nw;
					g[v][e.rev].flow-=nw;
					return nw;
				}
			}
		}
		return 0;
	}

	int max_flow(int _s, int _t)
	{
		s=_s;
		t=_t;
		int flow=0;
		while(bfs())
		{
			memset(done,0,sizeof(done));
			while(int nw=dfs(s,INF)) flow+=nw;
		}
		return flow;
	}
} ;

dinic flow ;