a836568125 @ 2024-10-09 19:10:46
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int cnt=0;
struct edge{
int to;
int next;
long long capacity;
edge(int to,int next,long long c):to(to),next(next),capacity(c){}
};
vector<int>head;
vector<edge>edges;
vector<int>level;
void add(int u,int v,long long c){
edges.push_back(edge(v,head[u],c));
head[u]=cnt;
cnt++;
}
void addedges(int u,int v,long long c){
add(u,v,c);
add(v,u,0);
}
bool bfs(int s,int t){
level.assign(head.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edges[i].next){
edge e=edges[i];
if(level[e.to]==-1&&e.capacity>0){
q.push(e.to);
level[e.to]=level[u]+1;
}
}
}
return level[t] != -1;
}
long long dfs(int s,int t ,long long flow){
if(s==t)
return flow;
long long ans=0;
for(int i=head[s];i!=-1;i=edges[i].next){
edge & e=edges[i];
if(e.capacity > 0 && (level[e.to] == level[s] + 1)){
long long f = dfs(e.to,t,min(flow,e.capacity));
ans+=f;
e.capacity-=f;
edges[i^1].capacity+=f;
flow-=f;
if(flow==0)
break;
}
}
return ans;
}
long long maxFlow(int s, int t) {
long long ans = 0;
while (bfs(s, t)) {
while (true) {
long long f = dfs(s, t, LLONG_MAX);
if (f == 0) {
break;
}
ans += f;
}
}
return ans;
}
int main(){
cin>>n>>m>>s>>t;
head.assign(n+1,-1);
for (int i = 0; i < m; ++i) {
int u, v;
long long c;
cin >> u >> v >> c;
addedges(u, v, c);
}
cout << maxFlow(s, t) << endl;
return 0;
}
by Joe2011 @ 2024-10-13 17:31:39
Cu ball