LuoguLOJ分析走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数,这个条件长得很像欧拉回路。我们首先把 $m$ 条关键边连上,然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点,显然相邻的两个间连一条边是最优的。这样子满足了度数限制。但是我们还需要让图连通。我们把所有连通块缩成一个点,然后求最小生成树,那么可以花费最小生成树上边权和的两倍的代价让图连通起来。时间复杂度 $...
UOJLuogu分析我们把速度看成点,铁路看成边,相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路,且加入的边从大到小连边的边数最小。既然要存在欧拉回路,那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上,然后根据每个点两个方向被覆盖的次数连一些边即可。然而欧拉回路还需要连通,所以我们还要求个 MST 把...
CodeforcesLuogu分析这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来,然后把欧拉回路上的边依次正向、反向定向即可。这个很容易造,我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数,再连一个自环即可。显然这样子边数是最小的。代码// ==================================== //...
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案,可以发现只有以下三种情况:团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外,于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$,则一定存在一段和为 $w-2$,...
LuoguLOJ分析考虑二分答案,则我们需要判定是否存在混合图欧拉回路。首先混合图不连通的话一定不存在。然后给无向边任意定向,算出每个点的度数,如果有点度数为奇数则不存在。那么对于一条无向边,假设我们定向 $u\to v$,则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。因此可以考虑网络流。对于 $in_ out_i$ 的点,从源点...
CodeForcesLuogu翻译分析记红色的区间为$1$,蓝色的区间为$-1$,那么对于任意一个点,覆盖它的线段的权值和的绝对值不超过$1$。那么可以对于每个区间 $[l,r]$ ,从 $l$ 向 $r+1$ 连无向边。此时也就变成了每个点的入度与出度之差的绝对值不超过$1$。发现奇度数点不太好搞。可以按照横坐标排个序,然后一一匹配。这样子只要求一条欧拉回路就行了。求出欧拉回路后给每条边染...
Luogu算法建图求欧拉路即可。代码#include <bits/stdc++.h> #define re register using namespace std; const int MAXN=256; int G[MAXN][MAXN]; int degree[MAXN]; char ans[MAXN*MAXN]; char tmp[MAXN]; int n; inli...