蓝桥杯算法提高VIP-传染病控制 （C++代码）

解题思路:





注意事项:





参考代码:

九十多行代码：

#include<iostream>
#include<cstdio>
using namespace std;
struct node
{
    int next[1000];//与该点相邻的点（建树前用） 
    int dep;//该点深度（建树后用） 
    int nextnum;//与该点相邻的点的数量（建树前用）
    int father;//该点的父亲（建树后用） 
}tree[1000];//保存树的信息 
int n,p,y,x,numd[10000],maxdep,depth[1000][1000],minn=99999;
bool f[401],ff[401],pd;
bool find(int x)
{
    if (x==1)//如果已经找到顶了，说明这一条路径上都没有之前没剪过的树枝 
    {
        pd=false;//打个标记 
        return true;
    }
    if (!ff[tree[x].father]||tree[x].father==1)
        find(tree[x].father);
    if (pd)    return false;
    else    return true;
}
//找当前边的祖先是否被剪过 
void dfs(int x,int d)
{    tree[x].dep=d;
    ++numd[d];//numd保存深度为d的点的个数 
    depth[d][numd[d]]=x;//depth[d][i]表示深度为d的第i个点是什么 
    maxdep=max(maxdep,d);
    int i;
    for (i=1;i<=tree[x].nextnum;++i)
    {
        if (f[tree[x].next[i]])    continue;//不能当前点的父亲当他的儿子（有点绕） 
        tree[tree[x].next[i]].father=x;
        f[tree[x].next[i]]=true;
        dfs(tree[x].next[i],d+1);
    }
}
//建树 
void doit(int d,int ans)
{
    if (ans>minn)//如果感染人数已经超过之前的最小答案了，不用做了，反正没意义 
        return;
    int i,j;
    if (d==maxdep+1)//如果所有层都搜完了，更新答案 
        minn=min(minn,ans);
    else
    {
        int hh=0;
        for (i=1;i<=numd[d];++i)//找当前层有几个没被感染的    
        {
            pd=true;
            if (find(depth[d][i]))
            {
                ++hh;
                ff[depth[d][i]]=false;
            }
            else
                ff[depth[d][i]]=true;
        }
        if (hh==0)//如果当前全部都被保住了，就更新答案然后返回到上一层 
        {
            minn=min(minn,ans);
            return;
        }
        for (i=1;i<=numd[d];++i)//当前层一个人一个人的依次救试试 
        {
            if (ff[depth[d][i]])
                continue;
            ff[depth[d][i]]=true;
            doit(d+1,ans+hh-1);
            ff[depth[d][i]]=false;
        }    
    }
}
//每层枚举要剪的树枝然后剪掉，搜下一层。注意如果祖先被剪过则该树枝不能剪 
int main()
{
    scanf("%d%d",&n,&p);
    for (int i=1;i<=p;++i)
    {
        scanf("%d%d",&x,&y);
        tree[x].next[++tree[x].nextnum]=y;
        tree[y].next[++tree[y].nextnum]=x;
    }
    f[1]=true;
    tree[1].father=1;
    dfs(1,1);
    doit(1,1);
    printf("%d",minn);
}