NOIp 2017 宝藏

Cobalt · 2018-09-25 21:50:26 · 个人记录

洛谷 P3959

Prim + 随机化

#include<iostream>
#include<cmath>
#include<algorithm> 
#define N 13
#define c 100000
#define inf 99999999
using namespace std;
int a[N][N],dis[N],from[N],depth[N],n,m,ans=inf;
inline void simulate_anneal(int s){
    int res=0;
    for(int i=1;i<=n;i++)
        a[i][i]=0,dis[i]=inf;
    for(int i=1;i<=n;i++)
        dis[i]=a[s][i],from[i]=s,depth[i]=2;
    depth[s]=1;
    for(int p=1;p<=n-1;p++){
        int vmin=inf,x;
        for(int i=1;i<=n;i++){
            if(dis[i]&&dis[i]<vmin){
                vmin=dis[i];
                x=i;
            }
        }
        for(int i=1;i<=n;i++){
            int rnd=rand()%n;
            if(dis[i]!=inf&&dis[i]&&i!=x&&rnd<1){
                //随机化 
                x=i;
                break;
            }
        }
        res+=dis[x];
        dis[x]=0;
        for(int i=1;i<=n;i++){
            if(dis[i]==a[x][i]*depth[x]&&depth[x]<depth[from[i]])
                from[i]=x,depth[i]=depth[x]+1;
            if(dis[i]>a[x][i]*depth[x])
                dis[i]=a[x][i]*depth[x],from[i]=x,depth[i]=depth[x]+1;
        }
    }
    ans=min(res,ans);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=inf;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(a[u][v]>w)
            a[u][v]=a[v][u]=w;
    }
    for(int i=1;i<=1000;i++)
        simulate_anneal(rand()%n+1);//如果没有随机出发点会WA很多点 
    cout<<ans;
    return 0;
}