P6628 [省选联考 2020 B 卷] 丁香之路 欧拉路+最小生成树

题意：

戳这里

分析：

• 暴力

据说状压+特判有50分，但我只会暴搜+特判，所以只有20分（我好菜)

• 正解

前置芝士 ：欧拉路径，生成树

这道题目的边权给的很巧妙，由基本不等式可以推出

任意两点之间直接连边不会比通过其他点相连更劣

所以对于每一个人来说，最后的路径可以看成是一条欧拉通路，欧拉通路具有一个性质：恰好有 (0) 或 (2) 个奇度数顶点 ，在本题中这两个奇度数顶点就是 (s) 和 (i) ，我们就按照欧拉通路的性质，对于每一个除 (s,i) 以外的奇度数顶点，找到一个离他最近的奇度数顶点与它配对，最后使得这些点的度数都为偶数

但是，这样还没有完，因为可能存在一条边，右端点和左端点连边成环的情况，也就是说最后连接完的图可能被分为了多个连通块,那么我们考虑用最小的代价将图联通，也就是求一个最小生成树

复杂度(O(n^2log))

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	
	const int maxn = 2505;
	int fa[maxn],bel[maxn];
	int n,m,s;
	long long sum,ans;
	vector<int> v[maxn];
	struct edge
	{
		int frm,to,val;
		edge(){}
		edge (int frm,int to,int val):frm(frm),to(to),val(val){}
		bool operator <(const edge &b)const
		{
			return val<b.val;
		}
	};
	
	int find(int x)
	{
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	
	void work()
	{
		int a,b;
		n=read();m=read();s=read();
		for(int i=1;i<=n;i++) fa[i]=i;
		for(int i=1;i<=m;i++)
		{
			a=read();b=read();
			v[a].push_back(b);
			v[b].push_back(a);
			sum+=abs(a-b);
			fa[find(a)]=find(b);
		}
		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;
			v[s].push_back(i);v[i].push_back(s);
			fa[find(bel[s])]=find(bel[i]);
			int pre=0;ans=sum;
			for(int j=1;j<=n;j++)
			{
				if(v[j].size()&1)
				{
					if(pre)
					{
						ans+=j-pre;
						for(int k=pre;k<j;k++) fa[find(bel[k])]=find(bel[j]);
						pre=0;
					}
					else pre=j;
				}
			}
			vector<edge> e;
			for(int j=1;j<=n;j++)
			{
				if(v[j].size())
				{
					if(pre&&find(bel[j])!=find(bel[pre])) e.push_back(edge(bel[j],bel[pre],abs(j-pre)));
					pre=j;
				}
			}
			sort(e.begin(),e.end());
			for(int j=0,k=e.size();j<k;j++)
			{
				if(find(e[j].frm)!=find(e[j].to))
				{
					fa[find(e[j].frm)]=find(e[j].to);
					ans+=2*e[j].val;
				}
			}
			printf("%lld ",ans);
			v[s].pop_back();v[i].pop_back();
		}
	}

}

int main()
{
	zzc::work();
	return 0;
}