【洛谷P6628】丁香之路

题目

题目链接：https://www.luogu.com.cn/problem/P6628
春暖花开，万物复苏，随着疫情的逐渐过去，Yazid 带着他的 (n) 个好朋友来到 T 大校园参观游览。方便起见，我们将他们从 (1) 至 (n) 编号。
T 大校园的版图可以抽象成一张 (n) 个顶点的无向图（顶点编号从 (1) 至 (n)）。且对于任意两个不同顶点，设它们的编号分别为 (i, j(i eq j))，则它们之间有一条需要花费 (|i - j|) 单位时间通过的无向边。
丁香花是 T 大的校花之一。时下正值丁香花盛开之际，校园内的 (m) 条道路上都开有丁香花。Yazid 的朋友们对丁香花十分感兴趣，因此他们都希望遍历所有开有丁香花的 (m) 条道路。
Yazid 的朋友们从顶点 (s) 出发。其中，第 (i) 个朋友希望以顶点 (i) 为终点终止他的参观。与此同时，如上面所述，每个朋友都必须经过开着丁香花的 (m) 条道路各至少一次。
Yazid 的朋友不想太过疲累，因此他们希望花尽可能少的时间来完成他们的目标。
请你计算 Yazid 的朋友们分别需要花费多少单位时间完成他们的目标。
(nleq 2500,mleq frac{n(n-1)}{2})。

思路

首先因为这 (m) 条边是必须走的，所以可以直接让答案加上这些边的权值。那么我们的目的就是最小化其他路径的权值之和。
对于一条 (i o j)（(i<j)）的路径，其实可以看作是 (i o i+1 o cdots o j)。对于终点是 (t) 的询问，也就是需要我们添加若干这样长度为 (1) 的边，使得存在一条起点是 (s)，终点是 (t) 的欧拉路径。
存在欧拉路径的充要条件是起点和终点的度数为奇数，其他点的度数为偶数。那么我们先让 (s) 和 (t) 的度数都加一。依次枚举 (i)，如果此时 (i) 的度数是奇数，那么就连上 (i o i+1) 这一条边。
这样贪心选择后的代价肯定是最小的。但是现在选出的路径可能并不连通。用并查集缩点，再次枚举所有点 (i)，记上一个度数不为 (0) 的点是 (j)（因为度数为 (0) 的点干脆不经过就行），如果 (i) 和 (j) 所在的连通块不同，那么就增加一条长度为 (|i-j|) 的边连接两个连通块。最后求一下最小生成树即可。显然所需要增加的代价就是最小生成树权值的 (2) 倍。
时间复杂度 (O((n^2+m)log n))。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=2510,M=3200010;
int n,m,s,ans,sum,deg[N],deg1[N],father1[N],father[N];

struct edge
{
	int u,v,dis;
}e[M];

void prework()
{
	memcpy(deg,deg1,sizeof(deg));
	memcpy(father,father1,sizeof(father));
	ans=sum; m=0;
}

int find(int x)
{
	return x==father[x]?x:father[x]=find(father[x]);
}

bool cmp(edge x,edge y)
{
	return x.dis<y.dis;
}

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for (int i=1;i<=n;i++) father[i]=i;
	for (int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		deg1[x]++; deg1[y]++;
		father[find(x)]=find(y);
		sum+=abs(x-y);
	}
	memcpy(father1,father,sizeof(father));
	for (int i=1;i<=n;i++)
	{
		prework();
		deg[s]++; deg[i]++;
		for (int j=1;j<n;j++)
			if (deg[j]&1)
			{
				ans++; deg[j]++; deg[j+1]++;
				father[find(j)]=find(j+1);
			}
		for (int j=1,k=0;j<=n;j++)
			if (deg[j])
			{
				if (k && find(j)!=find(k))
					e[++m]=(edge){find(j),find(k),j-k};
				k=j;
			}
		sort(e+1,e+1+m,cmp);
		for (int j=1;j<=m;j++)
		{
			int x=find(e[j].u),y=find(e[j].v);
			if (x!=y) father[x]=y,ans+=2*e[j].dis;
		}
		cout<<ans<<" ";
		deg[s]--; deg[i]--;
	}
	return 0;
}