P1041 传染病控制——暴力遍历所有相同深度的节点

P1041 传染病控制

说实话这种暴力我还是头一次见，每次病毒都会往下传染一层；

数据范围小，我们可以直接枚举当前层保护谁就好了；

用vector 记录相同层数的节点；维护已经断了的点；

如果超出最底层或者都已经被保护就更新答案；

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn=;

vector<int> v[maxn];

int pre[maxn],last[maxn],other[maxn],l;

void add(int x,int y)

{

    l++;

    pre[l]=last[x];

    last[x]=l;

    other[l]=y;

}

int n,m;

int siz[maxn],dep[maxn];

int father[maxn];

int madep;

void dfs1(int x,int fa)

{

    siz[x]=;

    dep[x]=dep[fa]+;

    father[x]=fa;

    madep=max(madep,dep[x]);

    for(int p=last[x];p;p=pre[p])

    {

        int v=other[p];

        if(v==fa) continue;

        dfs1(v,x);

        siz[x]+=siz[v];

    }

}

int vis[maxn];

int ans;

void dfs(int x,int sum)

{

    if(x==madep+)

    {

        ans=min(ans,sum);

        return ;

    }

    bool flag=;

    for(int i=;i<v[x].size();i++)

    {

        if(vis[father[v[x][i]]])//chosen not ill

        {

            vis[v[x][i]]=;

        }

        else {

        vis[v[x][i]]=;

        flag=;

        }

    }

    if(!flag)

    {

        ans=min(ans,sum);

        return ;

    }

    for(int i=;i<v[x].size();i++)

    {

        int u=v[x][i];

        if(vis[u]) continue;

        vis[u]=;

        dfs(x+,sum-siz[u]);

        vis[u]=;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(x,y);

        add(y,x);

    }

    dfs1(,);

    for(int i=;i<=n;i++)

    {

        v[dep[i]].push_back(i);

    }

    ans=n;

    dfs(,n);

    printf("%d",ans);

    return ;

}