Stinger @ 2021-04-09 19:53:07
本地一直跑不出来,离谱
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long
const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
int to, nxt, cap;
} e[10005];
int head[205], dis[205], tot = 1, s, t;
bool mark[205];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int w) {
e[++ tot].to = v, e[tot].cap = w, e[tot].nxt = head[u], head[u] = tot;
e[++ tot].to = u, e[tot].cap = 0, e[tot].nxt = head[v], head[v] = tot;
}
bool bfs() {
memset(dis, 0x3f, sizeof dis);
memset(mark, 0, sizeof mark);
dis[s] = 0;
Q.push(s);
while (Q.size()) {
int u(Q.front());
mark[u] = false;
Q.pop();
for (int i(head[u]); i; i = e[i].nxt) {
int v(e[i].to);
if (dis[u] + 1 < dis[v] && e[i].cap) {
dis[v] = dis[u] + 1;
if (!mark[v]) Q.push(v), mark[v] = true;
}
}
}
return dis[t] <= 1e9;
}
int dfs(const int u, const int low) {
int flow(0);
if (u == t) return low;
for (int i(head[u]); i; i = e[i].nxt)
if (dis[e[i].to] == dis[u] + 1 && e[i].cap) {
int v(e[i].to);
if (flow = dfs(v, min(low, e[i].cap))) {
e[i].cap -= flow, e[i ^ 1].cap += flow;
return flow;
}
}
return 0;
}
int Dinic() {
int flow(0), t(0);
while (bfs())
while (t = dfs(s, INF)) flow += t;
return flow;
}
signed main() {
// freopen("P3376_9.in", "r", stdin);
int n, m;
scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
for (int i(1); i <= m; ++ i) {
int u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
if (u != v) AddEdge(u, v, w);
}
printf("%lld\n", Dinic());
return 0;
}