一般图带权多重匹配

考虑如果都是偶数的点，那么我们可以将每一点的连边划分为入边和出边，这样构成很多个欧拉回路。

对于每个点入度和出度相等，特别的，自环也可以计算在内。

这样就可以net-flow，跑一个最小费用最大流。

考虑加入某些奇点，这样形成的是欧拉路，无非就是枚举这个点增加的是入度还是出度，然后取最小值即可。

复杂度\(O(2^k\times n^2 |v|)\)。

排序

对于每个点的所有可能序列，我们只需要考虑其左右端点即可。

首先一个点的所有区间一定无包含，否则小区间一定更优。

那么现在就可以合并儿子，枚举第一个选什么，然后进行装压DP，求出可行的最小右端点即可。

复杂度\(O(2^k\times m\times log^2m)\)。

传染

一个朴素的思路是枚举所有点对，然后可到达的去连边，缩点之后没有入度的强联通分量的个数就是答案。复杂度\(O(n^2)\)。

算法瓶颈在于建边。

考虑到算法的实质是在枚举点对，然后搞出点对的关系。

我们可以换一种统计方式——点分治。

考虑如何建图，暴力还是去一个一个把能覆盖的点连边。考虑前缀优化建图。

将点按照覆盖能力排序，然后当前点一定能覆盖到之前点覆盖过的点，我们没必要一一连边，只需要向对应的前缀虚点连边即可。

复杂度\(O(nlog^2n)\)，瓶颈在于排序。