BZOJ3590:[SNOI2013]Quare – 题解

主要思路

我操这个题是真的有意思(做完后索然无味)。

肯定这个题状压 DP 没跑的,所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难,我们需要思考一个归纳的方式来构造一个双连通图。

继续阅读BZOJ3590:[SNOI2013]Quare – 题解

BZOJ2959:长跑 – 题解

主要思路

乍一看没办法维护图的最大点权和,但是注意到没有删边操作,且注意到一个双连通分量可以被缩点,所以我们可以用 LCT 来维护双连通分量。

考虑开两个并查集,一个是双连通分量的并查集,标号为 \(0\);另外一个是维护连通性的并查集,标号为 \(1\)。

继续阅读BZOJ2959:长跑 – 题解