记录编号	45588	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.187 s
提交时间	2012-10-24 17:29:48	内存使用	4.00 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <queue>
using namespace std;

int maxdeep,minnum=~0u>>1,waynum[310],wayto[310][310],deep[310],recnum[310],rec[310][310];
/*bool*/short used[310];
queue<int> que;

void dfs(int deepnow,int numnow)
{
	if (deepnow>maxdeep)
	{
		minnum=numnow;
		return;
	}
	int i,j,k,cut,poi,temp=numnow-1;
	bool flag=false;
	
	/*calculation for next depth and shortcut*/
	for (i=0;i<recnum[deepnow];i++)
		if (!used[rec[deepnow][i]])
			temp++;
	/*calculation for next depth and shortcut*/
		
	/*shortcut*/
	if (temp>=minnum)
		return;
	/*shortcut*/
	
	for (i=0;i<recnum[deepnow];i++)
	{
		
		/*possibility*/
		cut=rec[deepnow][i];
		if (used[cut])
			continue;
		flag=true;
		/*possibility*/
		
		used[cut]=true;
		for (j=0;j<recnum[deepnow];j++)
		{
			poi=rec[deepnow][j];
			if (used[poi])
			{
				for (k=0;k<waynum[poi];k++)
					if (deep[wayto[poi][k]]==deepnow+1)
						used[wayto[poi][k]]=true;
			}
		}
		dfs(deepnow+1,temp);
		for (j=0;j<recnum[deepnow];j++)
		{
			poi=rec[deepnow][j];
			if (used[poi])
			{
				for (k=0;k<waynum[poi];k++)
					if (deep[wayto[poi][k]]==deepnow+1)
						used[wayto[poi][k]]=false;
			}
		}
		used[cut]=false;
	}
	if (!flag)
		minnum=numnow;
}

int main(void)
{
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	int i,n,p,a,b,pos,to;
	cin>>n>>p;
	for (i=p;i>=1;i--)
	{
		cin>>a>>b;
		wayto[a][waynum[a]++]=b;
		wayto[b][waynum[b]++]=a;
	}
	que.push(1);
	used[1]=true;
	deep[1]=1;
	recnum[1]=1;
	rec[1][0]=1;
	while (!que.empty())
	{
		pos=que.front();
		for (i=0;i<waynum[pos];i++)
		{
			to=wayto[pos][i];
			if (!used[to])
			{
				used[to]=true;
				deep[to]=deep[pos]+1;
				if (maxdeep<deep[to])
					maxdeep=deep[to];
				rec[deep[to]][recnum[deep[to]]++]=to;
				que.push(to);
			}
		}
		que.pop();
	}
	memset(used,0,sizeof(used));
	dfs(2,1);
	cout<<minnum<<endl;
	return(0);
}