题解：P4966 基地建设

· · 题解

可怕的模拟退火。

题意

给定 n 个点，m 条边，第 i 条边的权值为 val_i。你需要将权值任意排列，排列后，第 i 条边连接 ((q^i\bmod 2^{32}+i\times val_i)\bmod n+n)\bmod n+1 和 ((q^i\bmod 2^{32}-i\times val_i)\bmod n+n)\bmod n+1 两个点，忽略自环。

你需要对于所有点 i，满足 i\in [1,n]，求出该联通块内其它点到该点的距离之和 w_i。对于所有 w_i，你需要使得其中的最大值最小。输出任意一种合法方案。

思路

这种混乱的式子令人无从下手，于是我们考虑模拟退火。

考虑每次随机扰乱权值 val 并求出当前最大距离和。

那么怎么求最大距离和？

一种朴素的做法是，每次建立新图并跑 Kruskal，最后会形成一片最小生成森林，枚举每个联通块中的所有点，求该联通块内其它所有点到它的距离。

这种做法的时间复杂度是 O\bigl(m \log m+n^2\bigr)，由于模拟退火需要进行大量迭代，这种做法会产生大量开销，所以我们考虑优化。

我们考虑每个联通块维护所有点到块内其他点的距离之和的最大值，Kruskal 在合并联通块时，考虑到对于两个联通块 a,b，设 w 表示当前考虑的边的权值。则如果将 a 合并入 b，则 a 中的所有点都会经过当前考虑的这条边，设两个联通块大小分别为 size_a,size_b，所以这一块的距离之和会加上 size_b\times w，把 b 合并入 a 同理。

设块内最大距离和为 dp_a,dp_b，假设我们将 b 合并入 a，则转移方程为 dp_a= \max (dp_a+size_b\times w,dp_b+size_a\times w)。

这种做法的时间复杂度是 O\bigl(m\log m+(n+m)\alpha(n)\bigr)，显然比最初的做法优上不少。

哦对了注意计算幂的时候要对 2^{32} 取模，记得开 unsigned，我这里用的是 uint32_t 和 uint64_t。

Code

#include<bits/stdc++.h>
#define int long long
#define ull uint32_t
using namespace std;
const int mod=4294967296,N=200,inf=1e18+7;
struct Edge{
    int u,v,w;
}g1[N];
int n,m,q,ans,tot,sum,ptot;
int val[N],best[N],fa[N],dp[N],siz[N];
ull fac[N];
mt19937 s(chrono::steady_clock::now().time_since_epoch().count());
inline int find(int x){ // 并查集
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline ull qpow(ull a,int b){ // 快速幂
    uint64_t ans=1,c=a;
    while(b){
        if(b&1) ans=(ans*c)%mod;
        c=(c*c)%mod;
        b>>=1;
    }
    return (ull)ans;
}
inline void build(int v[]){ // 建立新图
    tot=0;
    for(int i=1;i<=m;i++){
        ull p=(ull)fac[i],t=(ull)i*v[i],a=p+t,b=p-t;
        int x=(a%n+n)%n+1,y=(b%n+n)%n+1;
        if(x==y) continue;
        g1[++tot]={x,y,v[i]};
    }
}
inline bool cmp(Edge A,Edge B){
    return A.w<B.w;
}
inline int calc(int v[]){ // 计算最大距离和
    build(v);
    sort(g1+1,g1+tot+1,cmp);
    for(int i=1;i<=n;i++) dp[i]=0,fa[i]=i,siz[i]=1;
    for(int i=1;i<=tot;i++){
        int u=find(g1[i].u),v=find(g1[i].v),w=g1[i].w;
        if(u==v) continue;
        dp[u]=max(dp[u]+w*siz[v],dp[v]+w*siz[u]); // 状态转移
        fa[v]=u,siz[u]+=siz[v];
    }
    int mx=0;
    for(int i=1;i<=n;i++) if(find(i)==i) mx=max(mx,dp[i]);
    return mx;
}
inline void SA(){
    double T=100000.0,dT=0.999; // 调参很重要！
    if(s()%2) shuffle(val+1,val+m+1,s); // 构造初始解，概率随机整个序列
    else for(int i=1;i<=m;i++) val[i]=best[i]; // 概率继承当前最优解
    int cur=calc(val);
    if(cur<ans){
        ans=cur;
        for(int i=1;i<=m;i++) best[i]=val[i];
    }
    while(T>1e-4){
        int nx=s()%m+1,ny=s()%m+1;
        if(nx==ny){
            T*=dT;
            continue;
        }
        swap(val[nx],val[ny]);
        int nv=calc(val),dE=nv-cur;
        if(dE<0||exp((double)-dE/T)>(double)s()/(double)s.max()){
            cur=nv;
            if(cur<ans){
                ans=cur;
                for(int i=1;i<=m;i++) best[i]=val[i];
            }
        }
        else swap(val[nx],val[ny]);
        T*=dT;
    }
}
void init(){ // 预处理幂
    fac[0]=1;
    for(int i=1;i<=m;i++) fac[i]=(ull)((uint64_t)fac[i-1]*(ull)q);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    init();
    for(int i=1;i<=m;i++) cin>>val[i];
    for(int i=1;i<=m;i++) best[i]=val[i];
    ans=calc(val);
    while((double)clock()/CLOCKS_PER_SEC<=1.90) SA();
    cout<<ans<<"\n";
    for(int i=1;i<=m;i++) cout<<best[i]<<"\n";
    return 0;
}