记录编号	434821	评测结果	TTTTTTTTTT
题目名称	[NOIP 2003]传染病控制	最终得分	0
用户昵称	Hallmeow	是否通过	未通过
代码语言	C++	运行时间	10.000 s
提交时间	2017-08-08 20:01:27	内存使用	4.15 MiB

#include<iostream>  
#include<cstdio>  
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;  
#define pos(i,a,b) for(int i=(a);i<=(b);i++)  
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 1000  
int n,p;
struct haha{
	int next,to;
}edge[N];
int head[N],cnt=1,ch[N][N],size[N],fa[N],dep[N];
void add(int u,int v){
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
void dfs(int x){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to!=fa[x]){
			fa[to]=x;dep[to]=dep[x]+1;
			ch[x][++ch[x][0]]=to;
			dfs(to);size[x]+=size[to];
		}
	}
}
int ans=0x7fffffff;
bool cmp(const int &a,const int &b){
	return 2*size[a]+3*ch[a][0]>2*size[b]+3*ch[b][0];
}
void dfs2(int now,int sum){
	//if(sum>ans) return;
	if(ch[now][0]==0||ch[fa[now]][1]==now){
		ans=min(n-sum,ans);
		return;
	}
	sort(ch[now]+1,ch[now]+ch[now][0]+1,cmp);
	pos(i,1,ch[now][0]){
		int to=ch[now][i];
		dfs2(to,sum+size[ch[now][1]]);
	}
}
int main(){
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	scanf("%d%d",&n,&p);
	pos(i,1,p){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}
	dfs(1);
	dfs2(1,0);
	cout<<ans;
	while(1);
	return 0;
}
/*12 11
1 2
2 3
3 4
1 5
5 6
6 7
7 8
1 9
9 10
10 11
11 12
5
*/