P4966 题解

· · 题解

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