「题解」「联合省选 2020 B」丁香之路 lilac

联合省选 2020 B Day 2 T3,最小生成树 的题目。

题目链接:联合省选 2020 B D2T3/Luogu P6628/LibreOJ 3310

题目

题目描述

春暖花开,万物复苏,随着疫情的逐渐过去,Yazid 带着他的 $n$ 个好朋友来到 T 大校园参观游览。方便起见,我们将他们从 \(1\) 至 编号。

T 大校园的版图可以抽象成一张 $n$ 个顶点的无向图(顶点编号从 $1$ 至 $n$)。且对于任意两个不同顶点,设它们的编号分别为 $i,j$($i\ne j$),则它们之间有一条需要花费 $|i-j|$ 单位时间通过的无向边。

丁香花是 T 大的校花之一。时下正值丁香花盛开之际,校园内的 $m$ 条道路上都开有丁香花。Yazid 的朋友们对丁香花十分感兴趣,因此他们都希望遍历所有开有丁香花的 $m$ 条道路。

Yazid 的朋友们从顶点 $s$ 出发。其中,第 $i$ 个朋友希望以顶点 $i$ 为终点终止他的参观。与此同时,如上面所述,每个朋友都必须经过开着丁香花的 $m$ 条道路各至少一次。

Yazid 的朋友不想太过疲累,因此他们希望花尽可能少的时间来完成他们的目标。 请你计算 Yazid 的朋友们分别需要花费多少单位时间完成他们的目标。

数据范围

测试点编号$n=$其他特殊限制
$1\sim 3$$50$$m=9$
$4\sim 6$$m=15$
$7\sim 8$
$9\sim 10$$300$
$11$$1600$$m=0$
$12\sim 14$$m=1$
$15\sim 17$
$18\sim 20$$2500$

时空限制

题目编号时间限制空间限制
联合省选 2020 B D2T3$2\text{s}$$512\text{MiB}$

题解

本题有部分分做法。

解法 A(特殊情况)

测试点 $11$ 满足 $m=0$。


$m=0$ 时很简单,只要输出点 $i$ 到 $s$ 的距离即 $|s-i|$ 即可。

时间复杂度为 $\Theta(n)$,期望得分为 $5$ 分。

解法 B(特殊情况)

测试点 $12\sim 14$ 满足 $m=1$。


$m=1$ 时也很简单,我们不妨把这条边记作 $(u,v)$,那么从 $s$ 到 $i$ 必过这条边只有两种方案。

  1. $s\to u\to v\to i$。
  2. $s\to v\to u\to i$。

每个点算一下取最小值即可

时间复杂度为 $\Theta(n)$,期望得分为 $15$ 分。

解法 C(暴力)

对于 $50\%$ 的数据,$m\leq 15$。


我们不妨考虑分层图,把层的信息设定成经过 $m$ 条边的二进制状态,那么我们只要跑一边 $\texttt{Dijkstra}$ 即可。

时间复杂度为 $\Theta(2^mn(m+\log _ 2n))$,期望得分 $35$ 分,并没有想象中的 $50$ 分。

解法 D(优化暴力)

对于 $50\%$ 的数据,$m\leq 15$。


解法 C 的缺陷就在于它使用了 $\texttt{Dijkstra}$。

仔细考虑松弛操作的内涵,我们不难发现,到了一个点以后它已经不可能再被松弛了(这与这道题的边权设置有关)。我们直接 $\texttt{BFS}$ 更快。

时间复杂度为 $\Theta(2^mn)$,期望得分 $50$ 分。

解法 E(最小生成树)

首先,对于要求经过的 $m$ 条边,他们必须被经过,那么最短路就要算上他们的边权和。

此外,我们不妨把这 $m$ 条边看作只能经过一次。因为对于一条边 $(u,v)$,如果我们第二次经过它,可以将其看成在普通的路上走,边权不变,仍为 $|u-v|$。

对于每一个点 $t$,我们考虑分开求答案。

不难发现,我们要求的其实就是一颗以 $s$ 为根的树经过一大堆点后到达 $t$ 的路径,并且在这棵树上有一个独特的性质
$$\text{dis} _ {u,v}=w _ {u,v}$$

所以我们只要求最小生成树即可,对于之前的 $m$ 条边,我们可以提前扯出来,因为他们一定要经过,即一定是最小生成树的边,我们可以先处理好他们。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=2500+5;

int n,m,s;
int deg[MAXN],inDeg[MAXN];
bool vis[MAXN],tot;
vector<pair<int,int>/**/> E[MAXN];
ll sum;

int bak_fa[MAXN],bak_size[MAXN],bak_deg[MAXN];

namespace UnionFind{
	int fa[MAXN],size[MAXN];
	inline void Init(void){
		for(reg int i=1;i<=n;++i)
			fa[i]=i,size[i]=1;
		return;
	}
	inline int find(reg int x){
		if(x==fa[x])
			return x;
		else
			return fa[x]=find(fa[x]);
	}
	inline void merge(int a,int b){
		if(size[a]>size[b])
			swap(a,b);
		fa[a]=b;
		size[b]+=size[a];
		return;
	}
}

using namespace UnionFind;

inline ll Solve(reg int t){
	++inDeg[t];
	for(reg int i=1;i<=n;++i){
		vis[i]=false;
		fa[i]=bak_fa[i],size[i]=bak_size[i],deg[i]=bak_deg[i];
		E[i].clear();
	}
	if(s!=t)
		deg[s]^=1,deg[t]^=1;
	reg ll ans=sum;
	reg int last=0;
	for(reg int i=1;i<=n;++i)
		if(deg[i]==1){
			if(last){
				for(reg int j=last;j<i;++j){
					++ans;
					merge(find(j),find(j+1));
				}
				last=0;
			}
			else
				last=i;
		}
	reg int tot=0;
	for(reg int i=1;i<=n;++i)
		if(inDeg[i]){
			reg int x=find(i);
			if(!vis[x]){
				vis[x]=true;
				++tot;
			}
		}
	for(int l=1,r;l<n;l=r){
		r=l+1;
		if(!inDeg[l])
			continue;
		while(r<=n&&!inDeg[r])
			++r;
		if(inDeg[r])
			E[r-l].push_back(make_pair(l,r));
	}
	for(reg int i=1;i<n&&tot>1;++i)
		for(reg int j=0,size=E[i].size();j<size;++j){
			pair<int,int> p=E[i][j];
			reg int u=find(p.first),v=find(p.second);
			u=find(u),v=find(v);
			if(u!=v){
				merge(u,v);
				--tot;
				ans+=2*i;
				if(tot==1)
					break;
			}
		}
	--inDeg[t];
	return ans;
}

int main(void){
	n=read(),m=read(),s=read();
	inDeg[s]=1;
	Init();
	for(reg int i=1;i<=m;++i){
		reg int u=read(),v=read();
		sum+=abs(u-v);
		bak_deg[u]^=1,bak_deg[v]^=1;
		inDeg[u]=inDeg[v]=1;
		u=find(u),v=find(v);
		if(u!=v)
			merge(u,v);
	}
	for(reg int i=1;i<=n;++i)
		bak_fa[i]=fa[i],bak_size[i]=size[i];
	for(reg int t=1;t<=n;++t)
		printf("%lld%c",Solve(t),t==n?'\n':' ');
	return 0;
}