随机化贪心算法

· · 题解

一道十分经典的模板题，考虑使用随机化贪心。事实上，这种做法在考场上有助于我们在短时间内避开大码力，得到更多的分。

首先，对于一个节点，通过广搜（减少常数，不用深搜）查找在三棵树上和自己距离和最大的节点，很明显该节点的答案一定不会低于自己。于是，我们得到了一种方案：不断寻找与自己在三棵树上总距离最大的节点，并跳到那个节点上。

但这样很容易陷入一个局部最优解，于是要采用随机化：每次随机选取一个节点，从它出发走十次，记录每次的最大值，可以得到答案：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5;
static inline char gc(){
    static char buf[M+5];
    static int it,ed;
    if(it==ed)ed=(it=0)+fread(buf,1,M,stdin);
    return it==ed?EOF:buf[it++];
}
typedef long long ll;
static inline ll read(){
    static ll x,f;static char c;
    for(f=1,c=gc();c<48;c=gc())if(c=='-')f=-f;
    for(x=0;c>47;x=x*10+(48^c),c=gc());return x*f;
}
int ed[M],n,rt,a[N];
ll d[N],ans,now;
bitset<N>vs;
struct Tree{
    int ed[M],cnt,fa[N];ll w[M],dep[N];
    vector<int>lk[N];
    inline void AG(){
        ++cnt;lk[ed[cnt]=read()].push_back(cnt+1);
        lk[ed[cnt+1]=read()].push_back(cnt);
        w[cnt]=w[cnt+1]=read();++cnt;
    }
    void bfs(int x){
        static int q[N],l,r,y;
        q[l=r=1]=x;for(y=1;y<=n;++y)dep[y]=fa[y]=0;
        while(l<=r){
            x=q[l++],d[x]+=dep[x];
            for(int i:lk[x])
                if((y=ed[i])!=fa[x])
                    dep[y]=dep[x]+w[i],fa[q[++r]=y]=x;
        }
    }
}tr[3];
int main(){
    n=read();int i,x,y,z,endtime=3.8*CLOCKS_PER_SEC;
    for(x=1;x<=n;++x)a[x]=x;
    random_device rd;
    mt19937_64 rg(rd());
    shuffle(a+1,a+n+1,rg);
    for(x=0;x<3;++x)
        for(i=1;i<n;++i)
            tr[x].AG();
    while(i<=n&&clock()<endtime){
        x=a[i];
        for(i=1;i<=10;++i){
            for(z=1;z<=n;++z)d[z]=0;
            tr[0].bfs(x),tr[1].bfs(x);
            tr[2].bfs(x),vs[x]=1;
            for(y=0,z=1;z<=n;++z)
                if(d[z]>d[y])y=z;
            if(d[y]>ans)ans=d[y];
            if(vs[y])break;
            else x=y;
        }while(vs[a[i]])++i;
    }
    printf("%lld\n",ans);
    return 0;
}