Pandaland HDU – 6005 无向图最小环(最短路剪枝 / 最小生成树+lca)

题目链接:https://cn.vjudge.net/problem/HDU-6005

题目大意:给m条双向边,让你找一个最小环,一条路只能走一次。

比赛时想着删边枚举然后跑删掉的边的两端点的最短路加上删掉的那条边的边权就是一个环了,但是时间复杂度明显爆炸,想了想剪枝也减不了多少就没打,没想到真的是这么做,只要再跑最短路的时候优先队列队顶元素大于ans就不跑了,竟然也能跑过,不知道是数据水还是这种图本身就无法组成理论上复杂度那么高的图。

网上还有另一种做法是用最小生成树+lca做的,复杂度低的多,做法是先求一遍最小生成树,然后对其进行lca,由于树上任意两点间加上一条边就会构成一个环,于是枚举边然后lca两点距离加上枚举的那个边权就可以了。

代码还没写,等以后有空再补吧

发表评论

电子邮件地址不会被公开。 必填项已用*标注