题目背景

近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国*决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究清楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。

解题报告：

用时：1h40min，3WA，4TLE

首先花了一会证明了所有贪心都是错的，需要决策，感觉搜索状态很少，考虑搜索剪枝。搜索状态要选对：一层一层搜索，把一层的点都加入一个栈中，考虑选择哪一个点作为控制点，其他点的儿子都加入下一层的栈中，继续搜索，加上最优性剪枝和起始排个序，可以0.3s跑过

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <queue>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define gi(x) scanf("%d",&x)

using namespace std;

const int N=305;

int n,a[N][N],sz[N],m,ans=150,fa[N],maxdep=0;

il void priwork(int x,int last,int dep){

   int u;maxdep=Max(maxdep,dep);

   for(int i=1;i<=sz[x];i++){

      u=a[x][i];if(u==last)continue;

      fa[u]=x;priwork(u,x,dep+1);

   }

}

bool kmp(int i,int j){return sz[i]<sz[j];}

il void dfs(int dep,int *S,int tot,int siz){

   if(tot>=ans)return ;

   if(!siz){

      ans=Min(tot,ans);

      return ;

   }

   RG int x;

   int T[N],top=0;

   for(RG int i=1;i<=siz;i++){

      for(RG int j=1;j<=siz;j++){

         if(i==j)continue;

         x=S[j];

         for(RG int k=1;k<=sz[x];k++)

            if(a[x][k]!=fa[x])T[++top]=a[x][k];

      }

      dfs(dep+1,T,tot+siz-1,top);

      top=0;

   }

}

void work()

{

   cin>>n>>m;

   int x,y;

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

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

      a[x][++sz[x]]=y;

      a[y][++sz[y]]=x;

   }

   priwork(1,1,1);int S[N],top=0;

   for(int i=1;i<=sz[1];i++)S[++top]=a[1][i];

   sort(S+1,S+top+1,kmp);

   dfs(2,S,1,top);

   printf("%d\n",ans);

}

int main()

{

	work();

	return 0;

}