随机化

sun123zxy 2019-01-16 原文

OI界的玄学担当，骗分的首选妙招——随机化

来道例题：NOIP2003 传染病控制

贪心+随机化

首先想到了贪心

贪心的思路是在每次扩散前，切断当前层已被感染的节点的儿子中子节点最多的那一个，剩下的节点被传染。循环中统计感染节点个数

我不会告诉你这样就90pt了

然而虽然能得这么多分，不能改变贪心是错解的事实

于是用随机化乱搞，切断子节点最多的那个点的几率最大，切断子节点次多的几率小一点，切断第三大的几率又小一点……

重复搞个10000次就可以交了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<ctime>
using namespace std;

int n,m;
struct star{//链式前向星存边 
    int u,v;
}edge[5005];
int nxt[5005],last[5005];
void addedge(int u,int v){//加边 
    m++;
    edge[m]=(star){u,v};
}
void starinit(){//前向星初始化 
    for(int i=1;i<=n;i++) last[i]=-1;
    for(int i=1;i<=m;i++){
        int flag=edge[i].u;
        nxt[i]=last[flag];
        last[flag]=i;
    }
}
int jdn[5005],dep[5005];
void getdata(int id,int prt){//树上的一些数据的预处理 
    dep[id]=dep[prt]+1;//深度 
    int ans=0;
    for(int i=last[id];i!=-1;i=nxt[i]){
        int to=edge[i].v;
        if(to==prt) continue;
        getdata(to,id);
        ans+=jdn[to];
    }
    jdn[id]=ans+1;//子节点数 
}
int vis[5005];
int que[5005];//队列存感染点 
int head,tail;
int bak[5005];
bool bakcmp(int cx,int cy){//按子节点数排序 
    return jdn[cx]>jdn[cy];
}
int pcr=0;//每次随机化得到的答案 
void fire(){
    for(int i=1;i<=n;i++) vis[i]=0;
    head=0;tail=0;
    que[tail]=1;tail++;
    vis[1]=1;
    int cut=-1;//当前打算切断到哪个点的道路 
    pcr=1;
    for(int q=1;head<tail;q++){//q是层数 
        for(;head<tail;){
            int id=que[head];
            if(dep[id]!=q) break;//只拓展当前层节点 
            head++;//删掉已经拓展过的节点 
            if(id==cut) continue;//上回被切断的节点不拓展 
            for(int i=last[id];i!=-1;i=nxt[i]){
                int to=edge[i].v;
                if(vis[to]==1) continue;//如果已经拓展过了（父节点）就跳过 
                que[tail]=to;tail++;//拓展 
            }
        }
        int len=tail-head;
        if(len>0){
            pcr+=len;//答案更新 
            for(int i=head;i<tail;i++){
                bak[i+1-head]=que[i];
                vis[que[i]]=1;//标记已经拓展过的节点 
            }
            sort(bak+1,bak+1+len,bakcmp);//排个序方便随机化 
            int f=1;
            for(f=1;f<len;f++){//随机化乱搞 
                int p=rand()%n;
                if(p!=1) break;
            }
            pcr--;//不会传染到被切断的节点 
            cut=bak[f];//切断点更新 
        }
    }
}
int main(){
    srand(time(0));//万恶之源 
    int cirno;
    cin>>n>>cirno;
    m=0;
    for(int i=1;i<=cirno;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v);addedge(v,u);
    }
    starinit();
    dep[1]=1;
    getdata(1,-1);
    int ans=999999999;
    for(int i=1;i<=10000;i++){//来个10000次 
        fire();
        ans=min(ans,pcr);
    }
    cout<<ans;
    return 0;
}