最大流（dinic算法）模板
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
struct edge{ll v,cap,flow;};
ll n,m,s,t;
vector<edge> edges;
vector<ll> G[200+10];
bool vis[200+10];
ll d[200+10],cur[200+10];
void addedge(ll u,ll v,ll cap){
edges.push_back((edge){v,cap,0});
edges.push_back((edge){u,0,0});
G[u].push_back(edges.size()-2);
G[v].push_back(edges.size()-1);
}
bool bfs(){
fill(vis,vis+n+1,false);
queue<ll> Q;
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
ll u=Q.front();Q.pop();
for(ll i=0;i<G[u].size();i++){
edge& e = edges[G[u][i]];
if(!vis[e.v]&&e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
ll dfs(ll u,ll rq){
if(u==t||rq==0)return rq;
ll flow=0,f;
for(ll& i=cur[u];i<G[u].size();i++){
edge& e=edges[G[u][i]];
if(d[u]+1==d[e.v]&&(f=dfs(e.v,min(rq,e.cap-e.flow)))>0){
e.flow+=f;
edges[G[u][i]^1].flow-=f;
flow+=f;
rq-=f;
if(rq==0)break;
}
}
return flow;
}
ll maxflow(){
ll flow=0;
while(bfs()){
fill(cur,cur+n+1,0);
flow+=dfs(s,inf);
}
return flow;
}
int main(){
cin >> n >> m >> s >> t;
for(ll i=1;i<=m;i++){
ll u,v,w;
cin >> u >> v >> w;
addedge(u,v,w);
}
cout << maxflow() << endl;
return 0;
}
注意：数据多测的时候，不需要另外清空vis、d、cur数组，因为cur会在maxflow函数中被清空，vis会在bfs函数中被清空，d原来的值会在赋值的时候被覆盖掉，也就是说，只需清空edges、G数组即可(使用vector的clear方法）。