题解：P3376 【模板】网络最大流

/*
web flow dinic templet
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, S, T, dis[205], cur[205];
struct ed{
	int y, flo, id;
	//an edge from x to y with flow of flo remaining(0 if
	//it's a reverse edge) having a reverse edge at the
	//idth edge comming out of y
};
vector< ed > e[205];
int bfs(){
	//find the shortest path currently, basically
	//renew all the dis[i]
	//why?
	//because after a round of dfs, a few paths will now
	//reach it's maximum flow so we need to do furthur
	//augmenting only on the new shortest paths which
	//have to involve only paths that CAN STILL HAVE
	//A FLOW INCREASE which is obvious
	for(int i = 1; i <= n; i++){
		dis[i] = -1;
	}
	queue<int> q;
	q.push(S);
	dis[S] = 0;
	while(!q.empty()){
		//standard bfs
		int x = q.front();
		q.pop();
		for(auto i: e[x]){
			if(dis[i.y] == -1 && i.flo > 0){
				//if this node(i.y) isn't visited yet AND
				//this edge still have a flow > 0
				dis[i.y] = dis[x] + 1;
				//renew i.y's shortest path
				q.push(i.y);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		cur[i] = 0;
	}
	if(dis[T] == -1){
		//the minimum cut has been filled(as in there
		//is no path from S to T with all none filled
		//paths anymore)
		return 0;
	}
	return 1;
}
int dfs(int x, int flow){
	//we're currently at x with the flow currently comming
	//into x being flow
	//however do note the difference between the TOTAL
	//flow into x and the CURRENT flow into x, because
	//right now we're basically ignoring all the previous
	//flows as we already "shrank" the size of the edge
	//accordingly so we don't even have to worry about it
	
	if(x == T){
		//we're already done
		return flow;
		//the flow from this augumenting is flow so we
		//return that
	}
	int sum = 0;
	//the total flow increase this round from all
	//the different augumenting paths
	for(int i = cur[x]; i < e[x].size(); i++){
		int y = e[x][i].y;

		if(dis[y] == dis[x] + 1 && e[x][i].flo > 0){
			//y is the next point after x on the shortest
			//path AND there is still flow on this edge
			//(which i mean is a little redundent bc 
			//otherwise it wouldn't be on the shortest
			//path or it would already be skipped from
			//the previous renewing of cur[x] after
			//making it 0, so it would still be correct
			//without that sentence but wtv)
			int now = dfs(y, min(flow, e[x][i].flo));
			//now = the amount of flow increased
			e[x][i].flo -= now;
			//the amount that can flow through this edge
			//is now decreased by now
			e[y][e[x][i].id].flo += now;
			//the reverse edge of this current edge has
			//a flow increase of now
			
			//below is a very detailed explation on
			//the augmenting process
			{
			/*
			now this is quite difficult to understand so
			allow me to explain the 
			"cancellation operation"
			basically we can "cancel" some flow on a
			certain edge that we obtained from an earlier
			augmentation to achieve an increase on the
			total flow, and this is why we need the
			backward edges, basically changing from 
			"decreasing the flow from x to y" on edge the
			x y to "increasing the flow from y to x"
			on an imaginary edge that runs from y to x.
			but how will doing so increasd the total flow?
			to explain that, let's say we're currently
			at a backward edge, meaning the edge i from x
			to y ACTUALLY DOESN'T EXIST, instead there is
			only an edge from y to x, and on an earlier
			augmentation in a different dfs we increased
			the total flow by e[x][i].flo, so edge i, as
			the backward edge, is added by e[x][i].flo
			and that's the only reason why this edge is
			on the shortest path this time during the bfs
			
			now we're at i, and we found that going
			from y there is a path of flow "now"(we
			know that because we already did dfs(y))
			so now we want to do a little
			"redistributing" of flow. we decrease the flow
			through the original edge(the backward edge
			of i) by now, and let that flow go through
			the path we discovered by dfs(y) instead,
			so now we have a flow of "now" missing from
			the old path of x -> T we found from earlier
			augmentation, so we need to somehow fill that
			gap up, and guess what? the flow we have right
			now(the one we got from S -> x) can def do
			that because we know this value must be
			>= now!
			
			
			so that's how we increased the total flow
			from S to T by "now" AND why we need to 
			build a backward edge and increase it's
			remaining flow by "now" each time(so we
			can do cancellation by increasing "backward"
			flow which is basically decreasing foward
			flow) 
			*/
			}
			flow -= now;
			sum += now;
			//obviously, cuz we decreased the in ward
			//flow by "now" and increased total flow by
			//"now"
			if(flow <= 0)break;
		}
		cur[x] = i;
		//the first i paths of x is already augmented
		//we need to mark this so the next time we reach
		//x(which we actually might because during the
		//bfs we essentially found several shortest paths
		//which we're all augmenting right now) we won't
		//go through these again
		//u might wonder, what if next time the flow
		//comming into x is better(as in > than) the
		//flow we got this time? won't we want to go
		//the first i edges again? because we might be
		//able to send more flow through right? well no
		//because we only reached here to renew cur[x]
		//IF we FILLED the remaining flow completely,
		//otherwise we would've "break" already at
		//flow <= 0
	}
	return sum;
}
void dinic(){
	int ans = 0, now;
	while(bfs()){
		while(now = dfs(S, 10000000000000005)){
			//while there's still increase
			ans += now;
		}
	}
	cout<<ans<<endl;
}
signed main(){
	cin>>n>>m>>S>>T;
	for(int i = 1; i <= m; i++){
		int x, y, z;
		cin>>x>>y>>z;
		int xid = e[y].size();
		int yid = e[x].size();
		e[x].push_back({y, z, xid});
		e[y].push_back({x, 0, yid});
		//xid = the id of the reverse edge of s, which is
		//basically the id of the edge comming from y to
		//x which obviously is just the size of e[y]
		
		//same for yid
		
		//however we make the flow of the reverse edge 0
		//so we won't ever falsely go through it
	}
	dinic();
	return 0;
}