P6628-[省选联考 2020 B 卷] 丁香之路【欧拉回路,最小生成树】

时间：2023-03-09 02:02:23
P6628-[省选联考 2020 B 卷] 丁香之路【欧拉回路,最小生成树】

正题

题目链接:https://www.luogu.com.cn/problem/P6628

题目大意

给出\(n\)个点的一张完全无向图，\(i\sim j\)的边权是\(|i-j|\)。

然后给出\(m\)条必经边，和起点\(s\)。

求对于每个终点经过所有必经边的最短路径。

\(1\leq n\leq 2500,0\leq m\leq \frac{n(n-1)}{2}\)

解题思路

很经典的模型，首先起点和终点连一条边，然后考虑加最少的边使得有欧拉回路。

欧拉回路有两个条件，度数都是偶数很好满足，直接把相邻的奇点连边肯定最优，但是还需要满足连通的条件。

考虑到图上边权的特殊性，我们显然只需要使用形如\(i\sim i+1\)的边，而这些边没有必要替代之前新加的边。所以直接拿这些边跑剩下连通块的最小生成树就好了。

时间复杂度\(O(m+n^2\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=2510;

struct edge{

	int x,y,w;

}e[N];

int n,m,s,cnt,ans,k,B[N*N];

int deg[N],fa[N],pf[N],b[N<<1];

int find(int x)

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

void unionn(int x,int y){

	x=find(x);y=find(y);

	if(x!=y)fa[x]=y;

	return;

}

bool cmp(edge x,edge y)

{return x.w<y.w;}

int main()

{

	scanf("%d%d%d",&n,&m,&s);

	int sum=0;

	for(int i=1;i<=n;i++)fa[i]=i;

	for(int i=1,x,y;i<=m;i++){

		scanf("%d%d",&x,&y);

		unionn(x,y);deg[x]++;deg[y]++;

		B[++cnt]=x;B[++cnt]=y;sum+=abs(x-y);

	}

	B[++cnt]=s;sort(B+1,B+1+cnt);

	cnt=unique(B+1,B+1+cnt)-B-1;

	for(int i=1;i<=n;i++)pf[i]=find(i);

	deg[s]++;m=0;

	for(int t=1;t<=n;t++){

		deg[t]++;ans=sum;int last=0;

		for(int i=1;i<=cnt;i++)b[i]=B[i];

		k=cnt;b[++k]=t;

		sort(b+1,b+1+k);

		k=unique(b+1,b+1+k)-b-1;

		for(int i=1;i<=n;i++)fa[i]=pf[i];

		for(int i=1;i<=n;i++)

			if(deg[i]&1){

				if(last){

					for(int j=last;j<i;j++)unionn(i,j);

					ans+=i-last;last=0;

				}

				else last=i;

			}

		for(int i=1;i<k;i++)

			e[i]=(edge){b[i],b[i+1],b[i+1]-b[i]};

		sort(e+1,e+k,cmp);

		for(int i=1;i<k;i++){

			int x=find(e[i].x),y=find(e[i].y);

			if(x==y)continue;

			fa[x]=y;ans+=e[i].w*2;

		}

		printf("%d ",ans);deg[t]--;

	}

	return 0;

}