自动搬运

查看原文

来自洛谷，原作者为

	MeowScore 灌水Q群：782534512（欢迎来玩）

搬运于2025-08-24 22:05:45，当前版本为作者最后更新于2022-11-04 11:45:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

link

先把这个毒瘤题面翻译一下（汉译汉是吧）。

有 $n$ 个点，$m$ 条边。给出每条边的权值 $v$。但是这些边的权值顺序是不确定的，对于不同的权值排列顺序，可能会生成一个不同形态的图，生成方式是对于第 $i$ 条边，它连接着两个点 $x$ 和 $y$。

$$x=((q^i\bmod2^{32}+i\times v_i)\bmod n+n)\bmod n+1 $$$$y=((q^i\bmod2^{32}-i\times v_i)\bmod n+n)\bmod n+1 $$

运算方式为无符号整型运算。

求对于所有的权值排列生成的图，图的代价最少是多少，下面定义“图的代价”：

设 $d_{i,j}$ 表示图中从 $i$ 到 $j$ 的所有简单路径中，一条路径上的最大边权最小是多少。图的代价即为 $\max_{i=1}^{n}(\sum_{j=1}^{n}d_{i,j})$（其中 $j$ 与 $i$ 联通）。

考虑怎么做。直接枚举排列显然不可行，然而边权排列和图的形态之间的联系就靠着上面 $x$ 和 $y$ 那两个根本没什么好性质的式子，所以想快速确定一个优秀的排列也是困难的，这个时候考虑一些随机算法，比如，模拟退火。

想到了模拟退火之后，我们接下来要考虑的问题就是如何快速求解一张图的代价。

首先考虑一个性质：$d_{i,j}$ 等于最小生成树上 $i$ 到 $j$ 的简单路径上的最大边权。详见此题，容易用反证法证明该结论。（其实这个题是一个最小生成森林，为了方便下面只考虑一棵树）

直接爆搜是 $n^2$ 的，但是这样效率低下，只能以准确性为代价了。考虑更高效的做法，我们不对于每个点暴力求解，而是考虑每条边的贡献。我们不妨从大到小考虑每一条边，假设当前边权值为 $z$，断掉它之后原来的这个连通块变成了 $A$、$B$ 两个连通块，对于 $A$ 中的每个点，贡献都要加上 $z\times size_B$，$B$ 也同理。但是删边操作很难维护，不妨使用时间倒流的技巧，变成从小到大加边，并查集直接做，详见代码。

第一发没过，调高了降温系数就过掉了。加了卡时，并且喜提最劣解。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=210;
#define ll long long
#define ui unsigned int
#define db double
ui ksm(ui x,ui y){
	ui res=1;
	while(y){
		if(y&1)
			res=res*x;
		x=x*x;
		y/=2;
	}
	return res;
}
int n,m;
ui q;
struct dat{
	int x;
	int y;
	int z;
}g1[N],g2[N],g3[N];
int v[N],uf[N];
ll sz[N],val[N];
ll ans=1000000000000000;
int cmp(dat x,dat y){
	return x.z<y.z;
}
int find(int x){
	if(uf[x]==x)
		return x;
	return uf[x]=find(uf[x]);
}
int rec[N];
void gen(){
	for(int i=1;i<=m;i++){
		ui x=((ksm(q,(ui)i)+((ui)i*v[i]))%n+n)%n+1;
		ui y=((ksm(q,(ui)i)-((ui)i*v[i]))%n+n)%n+1;
		g1[i]={x,y,v[i]};
	}
}
ll calc(){
	gen();
	ll res=0;
	for(int i=1;i<=m;i++)
		g2[i]=g1[i];
	sort(g2+1,g2+m+1,cmp);
	for(int i=1;i<=n;i++)
		uf[i]=i;
	int tot=0;
	for(int i=1;i<=m;i++){
		int x=g2[i].x;
		int y=g2[i].y;
		int z=g2[i].z;
		int f1=find(x);
		int f2=find(y);
		if(f1==f2)
			continue;
		uf[f2]=f1;
		g3[++tot]=g2[i];
	}
	for(int i=1;i<=n;i++){
		val[i]=0;
		uf[i]=i;
		sz[i]=1;
	}
	for(int i=1;i<=tot;i++){
		int x=g3[i].x;
		int y=g3[i].y;
		int z=g3[i].z;
		int f1=find(x);
		int f2=find(y);
		val[f1]=max(val[f1]+z*sz[f2],val[f2]+z*sz[f1]);
		sz[f1]+=sz[f2];
		uf[f2]=f1;
		res=max(res,val[f1]);
	}
	if(res<ans){
		ans=res;
		for(int i=1;i<=m;i++)
			rec[i]=g1[i].z;
	}
	return res;
}
void simulate_anneal(){
	db T=1e5;
	db low=0.999;
	while(T>=1e-4){
		int X=rand()%m+1;
		int Y=rand()%m+1;
		ll nw=calc();
		swap(v[X],v[Y]);
		ll res=calc();
		if(res>nw){
			db del=res-nw;
			if((db)rand()/RAND_MAX>exp(-del/T))
				swap(v[X],v[Y]);
		}
		T*=low;
	}
}
int main(){
	srand(time(0));
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
		cin>>v[i];
	while(1.0*clock()/CLOCKS_PER_SEC<=1.8)
		simulate_anneal();
	cout<<ans<<'\n';
	for(int i=1;i<=m;i++)
		cout<<rec[i]<<'\n';
	return 0;
}