记录编号	181024	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.356 s
提交时间	2015-08-21 15:19:01	内存使用	2.17 MiB

#include<cstdio>
using namespace std;
int n,m,u,v,maxl,shu,first[333],a[333][333],deep[333],s[333];
bool p[333];
struct eage
{
	int v,next;
}o[222222];
inline void add(int u,int v)
{
	o[++shu].v=v;
	o[shu].next=first[u];
	first[u]=shu;
}
void dfs(int x,int dep)
{
	a[dep][++a[dep][0]]=x;
	if(!first[x])
	{
		s[x]=1;
		return;
	}
	for(int i=first[x];i;i=o[i].next)
	{
		dfs(o[i].v,dep+1);
		s[x]+=s[o[i].v];
	}
	++s[x];
}
void biaoji(int x)
{
	p[x]=1;
	for(int i=first[x];i;i=o[i].next)
		biaoji(o[i].v);
}
void del(int x)
{
	p[x]=0;
	for(int i=first[x];i;i=o[i].next)
		    del(o[i].v);
}
void dp(int dep,int sum)
{
	if(sum>maxl)
	    maxl=sum;
	for(int i=1;i<=a[dep][0];++i)
	    if(!p[a[dep][i]])
		{
			biaoji(a[dep][i]);
			dp(dep+1,sum+s[a[dep][i]]);
			del(a[dep][i]);
		}
}
int main()
{
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&u,&v);
		if(u<v)
			add(u,v);
		else
			add(v,u);
	}
	dfs(1,1);
	dp(2,0);
	printf("%d",n-maxl);
	//while(1);
}