洛谷6628 [省选联考 2020 B 卷]丁香之路
LuoguLOJ分析走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。时间复杂度 $...
标签 欧拉路 下的文章
- 首页
- 欧拉路
UOJ236 【IOI2016】railroad
UOJLuogu分析我们把速度看成点，铁路看成边，相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路，且加入的边从大到小连边的边数最小。既然要存在欧拉回路，那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上，然后根据每个点两个方向被覆盖的次数连一些边即可。然而欧拉回路还需要连通，所以我们还要求个 MST 把...
CF527E Data Center Drama
CodeforcesLuogu分析这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来，然后把欧拉回路上的边依次正向、反向定向即可。这个很容易造，我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数，再连一个自环即可。显然这样子边数是最小的。代码// ==================================== //...
POI2011 简要题解
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$，则一定存在一段和为 $w-2$，...
洛谷3511 [POI2010]MOS-Bridges
LuoguLOJ分析考虑二分答案，则我们需要判定是否存在混合图欧拉回路。首先混合图不连通的话一定不存在。然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。因此可以考虑网络流。对于 $in_ out_i$ 的点，从源点...
CF429E Points and Segments
CodeForcesLuogu翻译分析记红色的区间为$1$，蓝色的区间为$-1$，那么对于任意一个点，覆盖它的线段的权值和的绝对值不超过$1$。那么可以对于每个区间 $[l,r]$ ，从 $l$ 向 $r+1$ 连无向边。此时也就变成了每个点的入度与出度之差的绝对值不超过$1$。发现奇度数点不太好搞。可以按照横坐标排个序，然后一一匹配。这样子只要求一条欧拉回路就行了。求出欧拉回路后给每条边染...
洛谷P1341 无序字母对
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...