弧优化的两种赋值方式为什么一个对一个不对
查看原帖
弧优化的两种赋值方式为什么一个对一个不对
630992
djsavu楼主2022/3/12 12:36

如果把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;
}
2022/3/12 12:36
加载中...