题目链接
算法模板
最大流
#include <bits/stdc++.h>
using ll = long long;
const int MAXN = 205;
const int INF = 0x3f3f3f3f;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f) : from(u) , to(v) , cap(c) , flow(f) {}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,m,s,t;
std::cin >> n >> m >> s >> t;
s--,t--;
std::vector<Edge> edges;
std::vector<std::vector<int>> G(n);
std::vector<int> a(n),p(n);
auto add = [&] (int u,int v,int cap) {
edges.push_back({u , v , cap , 0});
edges.push_back({v , u , 0 , 0});
int sz = edges.size(); //第一这里定义了 'm' , 与外层的 m 冲突了
G[u].push_back(sz - 2);
G[v].push_back(sz - 1);
};
auto Maxflow = [&] (int s,int t) {
ll flow = 0;
while (true) {
fill(a.begin(),a.end(),0);
std::queue<int> Q;
Q.push(s);
a[s] = INF;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i = 0 ; i < G[x].size() ; ++i) {
Edge& e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow) {
p[e.to] = G[x][i];
a[e.to] = std::min(a[x] , e.cap - e.flow); //易错 a[x] 写成 a[e.to]
Q.push(e.to);
}
}
if (a[t]) break;
}
if(!a[t])
break;
for(int u = t ; u != s ; u = edges[p[u]].from) {
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
flow += a[t];
}
return flow;
};
for(int i = 0 ; i < m ; ++i) {
int u,v,w;
std::cin >> u >> v >> w;
--u , --v;
add(u , v , w);
}
std::cout << Maxflow(s , t) << '\n';
return 0;
}