题解 P1041 【传染病控制】

· · 题解

这是一篇乱搞（随机化）题解。

一个显然的贪心策略是，我们优先选择联通孩子最多的点，把它与根的边删去。

可以构造一组数据证明它的错误性。想象有一条非常长的链，但有个一个深度较小，却比较"宽"的点集。这个贪心会优先把链与根的路径删去，但一个更优的策略是把"宽"的点集删去，延后几次删去链。因为链每次只会扩展1。

所以考虑乱搞。借鉴随机化的思路，有一个较大概率选取子孙节点多的点，有一个较小概率选取其他的点。

对于每一层的点x1,x2,x3..，把它们全部拿出来，子节点y1,y2,y3...放入优先队列中。有较大概率选择y中子树大小最大的y，将它与x的这条路径删掉。 再把其他的y加入队列。重复操作。

注意每次选取之前优先队列都要清空。

关于随机化次数，大概随机个500到1000次就可以稳稳过掉这一题了。(数据太水QAQ)

另外吐槽：我一开始想了个dp思路，煞有其事的推了一会。还认为很对(关键是没构造出能卡掉我的数据)。。最后发现错掉了。因为一般的dp状态并无法保证同一深度的边只会被选一次。

代码有点乱 codes:

#include<cstdio>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef pair<int,int> PII;
priority_queue<PII,vector<PII> >q;
const int N=305;
int dis[N],nxt[N<<1],v[N<<1],head[N],tot;
int siz[N],b[N],cnt,f[N];
int n,p,cur,ans=333;
inline void add(int x,int y){
    v[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
inline void dfs(int x,int fa){
    siz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=v[i];
        if(y!=fa){
            f[y]=x;
            dfs(y,x);
            siz[x]+=siz[y];
        }
    }
}
queue<int>Q;
inline void bfs(int s){
    while(!Q.empty())Q.pop();
    Q.push(s);
    while(!Q.empty()){//按层次扩展
        cnt=0;
        while(!q.empty())q.pop();
        while(!Q.empty()){//拿出同一层的所有点
            int x=Q.front();Q.pop();cur++;
            for(int i=head[x];i;i=nxt[i]){
                int y=v[i];//考虑子节点，加入优先队列
                if(y==f[x])continue;
                q.push(make_pair(siz[y],y));
                b[++cnt]=y;
            }
        }
        int t;
        if(!q.empty()){//乱搞过程，
            int y=q.top().second;q.pop();
            if(!q.empty()&&(rand()%N==0)){t=q.top().second;q.pop();}//较小概率选取次优解
            else t=y;
        }
        for(int i=1;i<=cnt;++i){
            int y=b[i];//把子节点的一层加入队列。
            if(y!=t)Q.push(y);
        }
    }
}
int main(){
    srand(20181108);
    scanf("%d%d",&n,&p);
    for(int i=1;i<=p;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,1);//预处理子树大小与深度
    for(int i=1;i<=1000;++i){//做他个1000次
        cur=0;
        bfs(1);
        ans=min(ans,cur);
    }
    printf("%d\n",ans);
    return 0;
}

@laduiw 是他，是他就是他切掉了这题。