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