题解：AT_arc085_c [ARC085E] MUL

· · 题解

前置：网络流、最大权闭合子图。

操作并集求贡献最值，可以考虑网络流。（这个数据范围就很符合。）

注意到这样一个事情：

如果一个宝石 x 碎了，那么它的倍数的宝石都一定碎了。

考虑它的逆否命题：如果一个宝石 x 没碎，那么它的约数的宝石都没碎。

所以一个宝石要有贡献，前提是所有约数编号的宝石都没碎。

每个 x 往其所有约数连一条边。

跑一遍最大权闭合子图即可。