弧优化的两种赋值方式为什么一个对一个不对

P3376 【模板】网络最大流

djsavu @ 2022-03-12 12:36:06

如果把cur[s]=first[s]和cur[v]=first[v]就ac了,但是用memcpy函数赋值就wa了,哪里有问题?

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 10010, E = 200010;

int n, m, s, t; LL ans = 0;
LL cnt = 1, first[N], nxt[E], to[E], val[E];
int cur[N];
inline void addE(int u, int v, LL w) {
    to[++cnt] = v;
    val[cnt] = w;
    nxt[cnt] = first[u];
    first[u] = cnt;
}
int dep[N], q[N], l, r;
bool bfs() {//顺着残量网络,方法是 bfs;这是个bool型函数,返回是否搜到了汇点 
    memset(dep, 0, (n + 1) * sizeof(int));//记得开局先初始化 
    //memcpy(cur, first, sizeof(first));
    q[l = r = 1] = s;//利用数组模拟队列,实现bfs,也可以利用stl里的队列
    dep[s] = 1;
    cur[s] = first[s];
    while (l <= r) {
        int u = q[l++];//左边界收缩,出队
        for (int p = first[u]; p; p = nxt[p]) {
            int v = to[p];
            if (val[p] and !dep[v]) {//按照有残量的边且没有被更新的点搜过去 
                cur[v] = first[v];
                dep[v] = dep[u] + 1;
                q[++r] = v;//右边界扩展,入队
            }
        }
    }
    return dep[t];//dep[t] != 0,就是搜到了汇点 
}
LL dfs(int u, LL in/*u收到的支持(不一定能真正用掉)*/) {
    //注意,return 的是真正输出的流量
    if (u == t)//能到达终点了就想进多少进多少
        return in;//到达汇点是第一个有效return 
    LL out = 0;
    for (int p = cur[u]; p and in; p = nxt[p]) {
        cur[u] = p;//记录当前增广到u顶点的哪条路了,以便下次直接从这条路开始以后的路开始增广,不用再增广前面已经增广了的路。
        int v = to[p];
        if (val[p] and dep[v] == dep[u] + 1) {//仅允许流向下一层 
            LL res = dfs(v, min(val[p], in)/*受一路上最小流量限制*/);
            //res是v真正输出到汇点的流量
            val[p] -= res;
            val[p ^ 1] += res;
            in -= res;
            out += res;
        }
    }
    //如果遍历完了所有能经过的点结果还是没有递归到u==t,即到达终点的情况,就说明源点和终点不联通。
    //这种情况(dfs到了不能再dfs下去的情况)就会到这个if语句。
    if (out == 0)//我与终点(顺着残量网络)不连通 
        dep[u] = -1;//上一层的点请别再信任我,别试着给我流量
//到达终点return in,中间节点return out
    return out;
}
int main() {
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 1; i <= m; ++i) {
        int u, v; LL w;
        scanf("%d %d %lld", &u, &v, &w);
        addE(u, v, w);
        addE(v, u, 0);
    }
    while (bfs())
        ans += dfs(s, 1e18);
    printf("%lld\n", ans);
    return 0;
}

by BootsH @ 2022-03-12 12:59:40

一个是 int 数组,一个是 long long


|