你是否还在写,假的欧拉回路 2
查看原帖
你是否还在写,假的欧拉回路 2
1064609
gty271828楼主2024/8/15 16:45

还是当前弧优化,以链式前向星为例。

第一种写法:

for (int i = now[u]; i; i = e[i].nxt) {
  now[u] = i;
  ...
}

第二种:

for (int i = now[u]; i; i = now[u]) {
  now[u] = e[i].nxt;
  ...
}

网络流中前者是对的,后者会跑得很慢,原因未知。

欧拉回路中后者是对的,前者跑得很慢,可以用一个菊花图状物(但不完全是)卡到 n2n ^ 2 以上,因为找欧拉路会走得很深很深,多次走到同一个点,以前者的写法每次都要遍历很多遍访问过的出边。

2024/8/15 16:45
加载中...