专栏文章

题解：AT_joisc2018_e 道路網の整備 (Road Service)

JJudgelight
AT_joisc2018_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqekluo
此快照首次捕获于
2025/12/04 03:31
3 个月前
此快照最后确认于
2025/12/04 03:31
3 个月前
查看原文
传送门
省流：纯随机爬山>精心设计初始状态模拟退火
注意到我们选菊花会比较优秀，所以我们选择重心当根，然后先选择度数最大的 kk 个点和根连边。然后我们爬山，每次纯随机一条边，尝试改一条边，算一下方案是否更优，直到符合题意为止。这么跑还是有点慢的，大概一组要跑 20min，但是我们注意到瓶颈在于每次 O(n2)O(n^2) 的计算，所以我们直接用到根的距离之和代替，这样快到飞起，跑一组大概只需要 5s 左右。
但是它算不出来第一组，所以我们在第一组直接随机选根，多算几次就出来了。
CPP
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 1009
#define db double
using namespace std;
const db p=18;
int n,k,w0,sz[N],rt;vector<int>V[N],E[N];
void dfs(int u,int from){
	sz[u]=1;for(auto v:V[u]){
		if(v==from)continue;
		dfs(v,u),sz[u]+=sz[v];
	}
	bool flag=(n-sz[u])<=n/2;for(auto v:V[u])flag&=(sz[v]<=n/2);
	if(flag)rt=u;
}
int dis[N];
int calc(int st){ 
	memset(dis,0x3f,sizeof(dis));
	queue<int>q;dis[st]=0,q.push(st);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(auto v:V[u])if(dis[v]>dis[u]+1)dis[v]=dis[u]+1,q.push(v);
		for(auto v:E[u])if(dis[v]>dis[u]+1){dis[v]=dis[u]+1,q.push(v);}
	}
	int ans=0;for(int i=1;i<=n;i++)ans+=dis[i];
	return ans;
}
int a[N];bool us[N];
vector<int>S;
db calc(){
	for(int i=1;i<=n;i++)E[i].clear();
	for(auto x:S)E[rt].eb(a[x]),E[a[x]].eb(rt);
	int ans=0;for(int i=1;i<=n;i++)ans+=calc(i);
	ans/=2;
	return min(p,p*pow(20,1.0-1.0*ans/w0));
}
int solve(vector<int>SS){
	for(int i=1;i<=n;i++)E[i].clear();
	for(auto x:SS)E[rt].eb(a[x]),E[a[x]].eb(rt);
	return calc(rt);
}
inline bool cmp(int x,int y){return V[x].size()>V[y].size();}
mt19937 rnd(time(0));
signed main(){
	scanf("%d%d%d",&n,&k,&w0);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),V[x].eb(y),V[y].eb(x);
	dfs(1,0);rt=rnd()%n+1;for(int i=1;i<=n;i++)a[i]=i;sort(a+1,a+n+1,cmp);
	for(int i=1,res=0;i<=n;i++)if(a[i]!=rt&&res<k)S.eb(i),res++;
	int times=0,last=solve(S);
	while(1){
		if(times%500==0){
			db nw=calc();
			if(nw+0.5>=p)break;
		}
		for(int i=1;i<=n;i++)us[i]=0;for(auto x:S)us[x]=1;
		vector<int>T;for(int i=1;i<=n;i++){
			if(!us[i]&&a[i]!=rt)T.eb(i);
		}
		vector<int>S1;int x=T[rnd()%T.size()],y=rnd()%S.size(),z=T[rnd()%T.size()],w=rnd()%S.size();
		while(z==x)z=T[rnd()%T.size()];while(w==y)w=rnd()%S.size();
		for(int i=0;i<S.size();i++)if(i!=y&&i!=w)S1.eb(S[i]);S1.eb(x),S1.eb(z);
		int nw=solve(S1);if(nw<last)last=nw,S=S1;
		times++;
	}
	for(auto x:S)printf("%d %d\n",rt,a[x]);
	return 0;
}
CPP
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 1009
#define db double
using namespace std;
const db p=18;
int n,k,w0,sz[N],rt;vector<int>V[N],E[N];
void dfs(int u,int from){
	sz[u]=1;for(auto v:V[u]){
		if(v==from)continue;
		dfs(v,u),sz[u]+=sz[v];
	}
	bool flag=(n-sz[u])<=n/2;for(auto v:V[u])flag&=(sz[v]<=n/2);
	if(flag)rt=u;
}
int dis[N];
int calc(int st){ 
	memset(dis,0x3f,sizeof(dis));
	queue<int>q;dis[st]=0,q.push(st);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(auto v:V[u])if(dis[v]>dis[u]+1)dis[v]=dis[u]+1,q.push(v);
		for(auto v:E[u])if(dis[v]>dis[u]+1){dis[v]=dis[u]+1,q.push(v);}
	}
	int ans=0;for(int i=1;i<=n;i++)ans+=dis[i];
	return ans;
}
int a[N];bool us[N];
vector<int>S;
db calc(){
	for(int i=1;i<=n;i++)E[i].clear();
	for(auto x:S)E[rt].eb(a[x]),E[a[x]].eb(rt);
	int ans=0;for(int i=1;i<=n;i++)ans+=calc(i);
	ans/=2;
	return min(p,p*pow(20,1.0-1.0*ans/w0));
}
int solve(vector<int>SS){
	for(int i=1;i<=n;i++)E[i].clear();
	for(auto x:SS)E[rt].eb(a[x]),E[a[x]].eb(rt);
	return calc(rt);
}
inline bool cmp(int x,int y){return V[x].size()>V[y].size();}
mt19937 rnd(time(0));
signed main(){
	scanf("%d%d%d",&n,&k,&w0);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),V[x].eb(y),V[y].eb(x);
	dfs(1,0);for(int i=1;i<=n;i++)a[i]=i;sort(a+1,a+n+1,cmp);
	for(int i=1,res=0;i<=n;i++)if(a[i]!=rt&&res<k)S.eb(i),res++;
	int times=0,last=solve(S);
	while(1){
		if(times%500==0){
			db nw=calc();
			if(nw+0.5>=p)break;
		}
		for(int i=1;i<=n;i++)us[i]=0;for(auto x:S)us[x]=1;
		vector<int>T;for(int i=1;i<=n;i++){
			if(!us[i]&&a[i]!=rt)T.eb(i);
		}
		vector<int>S1;int x=T[rnd()%T.size()],y=rnd()%S.size();
		for(int i=0;i<S.size();i++)if(i!=y)S1.eb(S[i]);S1.eb(x);
		int nw=solve(S1);if(nw<last)last=nw,S=S1;
		times++;
	}
	for(auto x:S)printf("%d %d\n",rt,a[x]);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...