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

,

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

Solution

感觉有点妙妙的题目。

首先显然是要求一个欧拉路径（起点和终点相同的情况是欧拉回路）。满足必须经过给定的边。有除了起点和终点度数为奇数外，其余点都是偶数。

我们把不满足度数要求的点称为坏点。

考虑把相邻的坏点连一条边。看上去这图就满足欧拉回路了。

但是手玩一下样例发现没有考虑不连通的情况。

只需要把在不同连通块的点做一个最小生成树。实现上，按照权值顺序枚举相邻点，如果两个点不在一个连通块就连起来。

有一个细节，在连相邻的坏点中，比如连接 $(i,j)$ ，一个显然的贪心就是把 $i,i+1,i+2,…,j$ 都连起来，这样权值最小，且让之后不同连通块的权值减小。不这么做会有一点问题。比如之间有一个需要走的点但不是坏点，到最后一步的时候代码认为他们不在一个连通块中导致权值又加了一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 3005
int fa[maxn];
int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int in[maxn],s[maxn][3];
struct yyy {
	int x,y;
}e[maxn*maxn];
int n,m,ss;ll SUM;
vector<pair<int,int> >O[maxn];
void merge(int x,int y) {
	if (getfa(x)^getfa(y)) fa[getfa(x)]=getfa(y);
}
int fl[maxn];
void solve(int S,int T) {
	int i,j;ll ans=SUM;
	for (i=1;i<=n;i++) fl[i]=in[i]=0,fa[i]=i,O[i].clear();
	for (i=1;i<=n;i++) in[i]=s[i][0],fa[i]=s[i][1],fl[i]=s[i][2];
	in[S]^=1,in[T]^=1;fl[S]=fl[T]=1;
	int las=0;
	for (i=1;i<=n;i++) if (in[i]) {
		if (!las) las=i;
		else {
			for (j=las;j<i;j++) merge(j,i);
			ans+=abs(i-las),las=0;
		}
	} 
	las=0;
	for (i=1;i<=n;i++) if (fl[i]) {
		if (las) O[abs(las-i)].push_back(mk(las,i));
		las=i;
	}
	for (i=0;i<=n;i++) {
		for (auto tmp:O[i]) 
			if (getfa(tmp.fi)^getfa(tmp.se)) {
				ans+=2*abs(tmp.fi-tmp.se);
				fa[getfa(tmp.fi)]=getfa(tmp.se);
			}
	}
	printf("%lld ",ans);
}
signed main(void){
	int i;
	read(n);read(m);read(ss);
	for (i=1;i<=m;i++) read(e[i].x),read(e[i].y),SUM+=abs(e[i].x-e[i].y);
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=1;i<=m;i++) {
		in[e[i].x]++,in[e[i].y]++;
		merge(e[i].x,e[i].y);
		fl[e[i].x]=1,fl[e[i].y]=1;
	}
	for (i=1;i<=n;i++) in[i]%=2,s[i][0]=in[i],s[i][1]=fa[i],s[i][2]=fl[i];
	for (i=1;i<=n;i++) solve(ss,i); 
	return 0;
}