求助当前弧优化上写法的神秘问题

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

CPP

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 ~ ms

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

CPP

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

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

CPP

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 ~ s

，像这样

CPP

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

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

猜测是没有正常退出循环，指针没有正常释放？

求助当前弧优化上写法的神秘问题

讨论操作

回复

相关推荐

求助当前弧优化上写法的神秘问题