P6628 [省选联考 2020 B 卷] 丁香之路

容易发现，按照题目要求走出的路径满足：给定 $m$ 条边所连的点 $deg \mod 2=0$ ，起点和终点 $deg\mod 2=1$。这个性质让我们联想到欧拉回路。

首先建出题目中给的 $m$ 条边和起点到终点的边，然后贪心地把度数为奇数的点和它的下一个点相连；如果这会使下一个点变成奇点，就继续把下一个点和下下一个点相连，以此类推。这样建边的代价一定是最小的，因为新建出的边边权都为1且互不相交。这样就满足了上面提到的度数限制。

但还有一个问题：这样建边后图可能会不连通。那么我们把已有的连通块用并查集缩点，然后求最小生成树，让图连通的最小代价就是最小生成树大小的两倍。总复杂度 $O((m+n^2)\log n)$

因为以上做法只与每个点的度数有关，所以在具体实现时，我们并不需要真的建出题目给定的边，只需记录这些边给点带来的度数即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace FGF
{
	int n,m,s;
	const int N=2505;
	struct edg{
		int u,v,w;
		edg(){};
		edg(int _u,int _v,int _w):u(_u),v(_v),w(_w){};
	};
	bool operator <(edg a,edg b)
	{
		return a.w<b.w;
	}
	int fa[N],bel[N],sum,du[N];
	int find(int x)
	{
		return x==fa[x]? x:fa[x]=find(fa[x]);
	}
	void work()
	{
		scanf("%d%d%d",&n,&m,&s);
		for(int i=1;i<=n;i++)fa[i]=i;
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			du[u]++,du[v]++;
			sum+=abs(u-v);
			fa[find(u)]=find(v);
		}
		for(int i=1;i<=n;i++)bel[i]=find(i);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)fa[j]=j;
			du[s]++,du[i]++;
			fa[find(bel[s])]=find(bel[i]);
			ll ans=sum,pre=0;
			for(int j=1;j<=n;j++)
				if(du[j]&1)
				{
					if(pre)
					{
						ans+=j-pre;
						for(int k=pre;k<j;k++)
							fa[find(bel[k])]=fa[find(bel[j])];
						pre=0;
					}
					else pre=j;
				}
			vector<edg> g;
			for(int j=1;j<=n;j++)
				if(du[j])
				{
					if(pre&&find(bel[j])!=find(bel[pre]))
						g.push_back(edg(bel[j],bel[pre],abs(j-pre)));
					pre=j;
				 } 
			sort(g.begin(),g.end());
			for(int sz=g.size(),j=0;j<sz;j++)
				if(find(g[j].u)!=find(g[j].v))
					fa[find(g[j].u)]=find(g[j].v),ans+=g[j].w*2;
			du[s]--,du[i]--;
			printf("%lld ",ans);
		}
	}
}
int main()
{
	FGF::work();
	return 0;
}

2024.10.14 更新： 修复格式

感觉这题的思路非常奇妙，就算会做了也完全不知道为啥要这么想。。。

题意

有一个 $n$ 个点的无向完全图，边 $i\leftrightarrow j$ 的边权为 $|i-j|$，强制经过指定的 $m$ 条边，求起点为 $s$，终点为 $i\in[1,n]$ 的最短路径。$n\le 2500,m\le \frac{n(n-1)}2$。

思路

考虑在一个可重无向边集 $E$，如果：

• $\text{必须经过的}\ m\ \text{条边}\subseteq E$
• 存在一条 $s\leftrightsquigarrow i$ 的欧拉路径

那么就有符合题目要求的一条路径存在。答案即为符合条件的 $\sum_{i\in E} w_i$ 的最小值。

一开始，我们就先把题目要求的 $m$ 条边加到 $E$ 里面，这样 $E$ 就天然满足第一个条件。

欧拉路径不太方便搞，我们一开始就往 $E$ 中加一个 $s\leftrightarrow i$，这样第二个条件就变成了“存在一条欧拉回路”。

存在欧拉回路的条件：

• $2\mid\deg(i),\forall i\in[1,n]$
• 图联通

下面说如何向 $E$ 中添加若干条边，使得 $E$ 满足上面两个条件，并且让这些边的边权和最小（先说做法，再写证明）

恢复度数奇偶性

把所有 $2\nmid\deg(i)$ 的 $i$ 拿出来，按编号排序。然后把相邻的奇度点两两配对（第 $2k$ 小的和第 $2k-1$ 小的配对）连边（图中红色为奇度点，蓝色为加的边）：

注：做法中所说的连边并不是说直接连 $u\leftrightarrow v$。而是连（这样连边显然更优）：

$$\begin{aligned} u&\leftrightarrow u+1\cr u+1&\leftrightarrow u+2\cr u+2&\leftrightarrow u+3\cr \vdots \cr v-1&\leftrightarrow v \end{aligned}$$

联通性

建完前文所述的边之后，图缩成若干连通块。只要再加一些边，把这些联通块联通起来即可，可以看出，这是一个类似最小生成树的东西：

把所有 $\deg(i)\neq0$ 的 $i$ 拿出来按编号排序（度数为 0 的点不需要被联通），把相邻的两个点之间的的边拿去做 Kruskal 即可。所有在最小生成树上的边都会被经过两次。

复杂度 $O(n^2 \log n+m)$。

证明

下证任何一组最优解 $E^{\prime}$ 必定可以转化成贪心方法得到的解 $E$。

首先，我们把初始加的边（题目要求的 $m$ 条边和 $s\leftrightarrow i$）称为黑边，其余的边叫白边。

引理

有且仅有一个 $E$ 满足：

• $E$ 包含指定的 $m+1$ 条黑边
• $E$ 中的白边边权都为 $1$
• $E$ 中没有白色重边
• 在只考虑 $E$ 中的边时，满足 $2\mid\deg(i)$

比较显然，证明略。

原结论证明

• 首先，把 $E^{\prime}$ 所有白边 $u\leftrightarrow v$ 都拆成若干 $i\leftrightarrow i+1$ 的边，显然不劣（详见前文）。
• 然后，重复以下过程，直到 $E^{\prime}$ 中不剩下任何一对白色重边：
  • 从 $E^{\prime}$ 找到一对白色重边
  • 把这对边从 $E^{\prime}$ 中删除
  • 把这条边加入 $G$ 中（只加一次即可）

感性理解：

• $E$ 中的白边对应恢复度数奇偶性过程中加的边
• $G$ 中的边对应做最小生成树过程中加的边

此时，如果只考虑 $E^{\prime}$ 中的边，必然满足 $2\mid\deg(i)$。

由引理，此时 $E^{\prime}$ 中的边，必定与恢复完度数奇偶性之后，$E$ 中的边相同。

$G$ 中的边的目的就是把 $E^{\prime}$ 形成的连通块缩到一起，与贪心做法中的 MST 是等价的。

证毕。