求助 当前弧优化 上写法的神秘问题
查看原帖
求助 当前弧优化 上写法的神秘问题
386597
柠檬熟了楼主2023/12/16 15:22

RT,我原来 当前弧优化 这一步是不取地址的写法

for (int i = Cur[x]; i && F < MAXF; i = E[i].nxt) {
	Cur[x] = i;
	if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
		long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
		if (!TmpF) Dep[E[i].to] = -1;
			F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
	}
	// if (F >= MAXF) break;
}

然后跑出来非常正常,大约 75 ms75 ~ ms

如果把 for 里面的第二个条件放到外面,像下面这样,时间也是对的

for (int i = Cur[x]; i; i = E[i].nxt) {
	Cur[x] = i;
	if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
		long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
		if (!TmpF) Dep[E[i].to] = -1;
			F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
	}
	if (F >= MAXF) break;
}

今天试了一下取地址的写法,当第二个条件在外面的时候,是对的

for (int &i = Cur[x]; i; i = E[i].nxt) {
	// Cur[x] = i;
	if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
		long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
		if (!TmpF) Dep[E[i].to] = -1;
			F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
	}
	if (F >= MAXF) break;
}

但是向第一段程序一样,把这个判断放到循环第一行,时间就假了,需要 1.15 s1.15 ~ s,像这样

for (int &i = Cur[x]; i && F < MAXF; i = E[i].nxt) {
	// Cur[x] = i;
	if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
		long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
		if (!TmpF) Dep[E[i].to] = -1;
			F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
	}
	// if (F >= MAXF) break;
}

按循环的执行顺序来说,好像放在循环内部最后和放在小括号第二条件是本质相同的啊,为什么会出现这种神秘现象?

猜测是没有正常退出循环,指针没有正常释放?

2023/12/16 15:22
加载中...