FateReset_ @ 2023-07-24 15:34:27
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
vector< vector<int> > e;
int fordFulkerson(int s, int t){
int u,v;
int max_flow=0;
vector<vector<int>> rGraph=e;
while(true){
vector<int> parent(n,-1);
queue<int> q;
q.push(s);
parent[s]=-2;
while (!q.empty() && parent[t]==-1){
int cur=q.front();
q.pop();
for(int i=1;i<=n;i++){
if(rGraph[cur][i]>0 && parent[i]==-1){
parent[i]=cur;
q.push(i);
}
}
}
if(parent[t]==-1) break;
int path_flow=INT_MAX;
for(v=t;v!=s;v=parent[v]){
u=parent[v];
path_flow=min(path_flow, rGraph[u][v]);
}
for(v=t;v!=s;v=parent[v]){
u=parent[v];
rGraph[u][v]-=path_flow;
rGraph[v][u]+=path_flow;
}
max_flow+=path_flow;
}
return max_flow;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
e.resize(n + 1, vector<int>(n + 1, 0));
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u][v]=w;
}
cout<<fordFulkerson(s,t);
return 0;
}
by FateReset_ @ 2023-07-24 15:35:38
评测记录