求助网络流

P3376 【模板】网络最大流

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);

因为如果按照你的写法的话在最后更新时 flow[t]0,就是死循环


|