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

· · 题解

传送门

省流：纯随机爬山>精心设计初始状态模拟退火

注意到我们选菊花会比较优秀，所以我们选择重心当根，然后先选择度数最大的 k 个点和根连边。然后我们爬山，每次纯随机一条边，尝试改一条边，算一下方案是否更优，直到符合题意为止。这么跑还是有点慢的，大概一组要跑 20min，但是我们注意到瓶颈在于每次 O(n^2) 的计算，所以我们直接用到根的距离之和代替，这样快到飞起，跑一组大概只需要 5s 左右。

但是它算不出来第一组，所以我们在第一组直接随机选根，多算几次就出来了。

#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;
}
#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;
}