如果您 RE 20
查看原帖
如果您 RE 20
236866
401rk8楼主2021/12/17 20:59

您应该是使用了 vector 等存储需要撤销的边,然后撤销时正序扫描,这样如果一条边加入后又删除就会在撤销时出错(会删除一条不存在的边)

void modify(int i,int j) {
	mst -= e[j].w, lct.cut(j+n,e[j].u), lct.cut(j+n,e[j].v);
	mst += e[i].w, lct.link(i+n,e[i].u), lct.link(i+n,e[i].v);
}

for(auto i : re[u]) modify(i.se,i.fi); // RE
for(auto i = re[u].rbegin(); i != re[u].rend(); ++i) modify(i->se,i->fi); // AC

所以不要想不开用 vector,最好用栈,常数小且不易出错

3
1 2 50
1 3 20
2
2 3 30 3 3
2 1 10 1 3
2021/12/17 20:59
加载中...