记录编号	434750	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.164 s
提交时间	2017-08-08 19:14:14	内存使用	0.68 MiB

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstring>
#include <cmath>
using namespace std;
int n,p,x,y,zz,st[1005],maxdeep,tot,peo;
int deep[305][305],dad[305],size[305];
bool vis[305];
struct node{int to,next;}e[1005];
void add(int x,int y){
	 e[++zz].next=st[x];
	 e[zz].to=y;
	 st[x]=zz;
}
void dfs(int x,int dep,int fa){
	 deep[dep][++deep[dep][0]]=x;//每一层深度对应的点，相当于被感染的时间 
	 maxdeep=max(maxdeep,dep);
	 dad[x]=fa;
	 size[x]=1;
	 for(int i=st[x];i;i=e[i].next){
	 	 int t=e[i].to;
	 	 if(t!=fa){
		   dfs(t,dep+1,x);
	       size[x]+=size[t];
         }
	 }
}	
void dfs1(int dep){
	 bool end=0;
     for(int i=1;i<=deep[dep][0];i++){
	     int t=deep[dep][i];
		 if(vis[dad[t]]) vis[t]=1;//父亲生存，儿子生存 
	 }
	 for(int i=1;i<=deep[dep][0];i++){
	     int t=deep[dep][i];
	     if(!vis[t]){
	     	vis[t]=1;//切除通向t的途径（t及其子树生存）
			peo+=size[t]; //得以生存的人数 
	     	dfs1(dep+1);
	     	vis[t]=0;//回溯 
	     	peo-=size[t];//回溯 
	     	end=1;//还有子树，可继续感染 
	     }
	 }
	 for(int i=1;i<=deep[dep][0];i++){
	     int t=deep[dep][i];
		 if(vis[dad[t]]) vis[t]=0;
	 }//回溯儿子 
	 if(!end) tot=max(tot,peo);
}
int main(){
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	scanf("%d%d",&n,&p);
	for(int i=1;i<=p;i++){
	    scanf("%d%d",&x,&y);
	    add(x,y);add(y,x);
	}
	tot=1;
	dfs(1,1,0);
	dfs1(2);
	printf("%d",n-tot);
}