GossWandering @ 2021-05-03 22:42:18
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 210, M = 5010;
int n, m, s, t;
int Edgecnt = 1, head[N], nxt[M * 2], to[M * 2];
int vis[N], pre[N];
LL flow[N], edge[M * 2], maxflow;
void add(int u, int v, int w)
{
Edgecnt ++ ;
to[Edgecnt] = v;
edge[Edgecnt] = 1ll * w;
nxt[Edgecnt] = head[u];
head[u] = Edgecnt;
}
int bfs()
{
memset(vis, 0, sizeof vis);
queue<int> q;
q.push(s); vis[s] = 1;
flow[s] = 1e18;
while (!q.empty())
{
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i])
{
int y = to[i]; LL z = edge[i];
if (z > 0 && !vis[y])
{
flow[y] = min(flow[y], z);
pre[y] = i;
q.push(y);
vis[y] = 1;
if (y == t) return 1;
}
}
}
return 0;
}
void update()
{
int x = t;
while (x != s)
{
int i = pre[x];
edge[i] -= flow[t];
edge[i ^ 1] += flow[t];
x = to[i ^ 1];
}
maxflow += flow[t];
}
int main()
{
scanf("%d %d %d %d", &n, &m, &s, &t);
for (int i = 1; i <=m; i ++ )
{
int x, y, c;
scanf("%d %d %d", &x, &y, &c);
add(x, y, c);
add(y ,x, 0);
}
while (bfs()) update();
printf("%lld\n", maxflow);
return 0;
}
为什么此代码碰到样例会死循环?
by yzy_rick @ 2021-06-20 12:56:09
把
flow[y] = min(flow[y], z);
改成
flow[y] = min(flow[x], z);
因为如果按照你的写法的话在最后更新时