记录编号	104392	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2014-06-09 09:28:12	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=310,INF=0x7fffffff/2;
int N,M;
vector<int> c[SIZEN];
int depth[SIZEN]={0};
int H=0;
int father[SIZEN]={0};
vector<int> level[SIZEN];
bool infect[SIZEN]={0};
int tsize[SIZEN]={0};
int ans=INF;
void search(int now,int x){//切掉第x层某个点和它父亲的边
	if(now>=ans) return;
	if(x==H+1){
		ans=min(ans,now);
		return;
	}
	vector<int> st;
	for(int i=0;i<level[x].size();i++){
		int v=level[x][i];
		if(infect[father[v]]){
			st.push_back(v);
			infect[v]=true;
		}
	}
	if(!st.size()){
		ans=min(ans,now);
		return;
	}
	for(int i=0;i<st.size();i++){
		int v=st[i];
		infect[v]=false;
		search(now+st.size()-1,x+1);
		infect[v]=true;
	}
	for(int i=0;i<st.size();i++) infect[st[i]]=false;
}
void DFS(int x){
	level[depth[x]].push_back(x);
	H=max(H,depth[x]);
	for(int i=0;i<c[x].size();i++){
		int v=c[x][i];
		if(v==father[x]) continue;
		father[v]=x;
		depth[v]=depth[x]+1;
		DFS(v);
		tsize[x]+=tsize[v];
	}
	tsize[x]++;
}
void read(void){
	scanf("%d%d",&N,&M);
	int a,b;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b),c[b].push_back(a);
	}
}
int main(){
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	read();
	DFS(1);
	infect[1]=true;
	search(1,1);
	printf("%d\n",ans);
	return 0;
}