洛谷6628 [省选联考 2020 B 卷]丁香之路
Luogu LOJ 分析 走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。 我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。 但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。 时...
Luogu LOJ 分析 走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。 我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。 但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。 时...
UOJ Luogu 分析 我们把速度看成点，铁路看成边，相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路，且加入的边从大到小连边的边数最小。 既然要存在欧拉回路，那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上，然后根据每个点两个方向被覆盖的次数连一些边即可。 然而欧拉回路还需要连通，所以我们还要求个 ...
Codeforces Luogu 分析 这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来，然后把欧拉回路上的边依次正向、反向定向即可。 这个很容易造，我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数，再连一个自环即可。显然这样子边数是最小的。 代码 // =================================...
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
Luogu LOJ 分析 考虑二分答案，则我们需要判定是否存在混合图欧拉回路。 首先混合图不连通的话一定不存在。 然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。 那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。 因此可以考虑网络流。对于 $in_ out_i$...
Luogu LOJ 分析 每个集合是否合法很容易判，先把这个东西预处理出来，记为 $chk_S$ 。 设 $f_S$ 表示集合 $S$ 的答案，那么有： 子集卷积即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==========...