传染病控制(暴力搜索)

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 307
#define INF 0x3f3f3f
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x * f;
}
int n,cnt,mxdep,ans=INF;
int head[N],fth[N],sz[N],vis[N];
int deep[N][N];
struct Edge {
    int next,to;
}edge[N<<1];
inline void add(int u,int v) {
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    head[u] = cnt;
}
void Dfs_first(int u,int fa,int dep) {
    mxdep = max(mxdep,dep);
    sz[u] = 1; fth[u] = fa; deep[dep][++deep[dep][0]] = u;
    for(int i=head[u];i;i=edge[i].next) {
        int v = edge[i].to;
        if(v==fa) continue;
        Dfs_first(v,u,dep+1); sz[u] += sz[v]; 
    }
}
void make_mark(int u,int tag) {
    vis[u] = tag;
    for(int i=head[u];i;i=edge[i].next) {
        int v = edge[i].to;
        if(v!=fth[u]) make_mark(v,tag);
    }
}
void Dfs(int dep,int tot) { //从2开始搜 
    if(dep==mxdep+1) {
        ans = min(ans,tot); return ;
    }
    int flag = 0;
    for(int i=1;i<=deep[dep][0];++i) {
        if(vis[deep[dep][i]]) {
            ++flag; continue;
        }
        make_mark(deep[dep][i],1);
        Dfs(dep+1,tot-sz[deep[dep][i]]);
        make_mark(deep[dep][i],0);
    }
    if(flag==deep[dep][0]) ans = min(ans,tot);
}
int main()
{
    n = read(); int m = read();
    for(int i=1,u,v;i<=m;++i) {
        u = read(), v = read();
        add(u,v), add(v,u);
    }
    Dfs_first(1,0,1);
    Dfs(2,n);
    printf("%d\n",ans);
//    printf("\n\ntest\n\n maxdep=%d",mxdep);
    return 0;
}