记录编号	546785	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	牛掰格拉斯	是否通过	通过
代码语言	C++	运行时间	0.578 s
提交时间	2019-11-12 21:24:22	内存使用	13.68 MiB

//2019.11.12
//方法：按层暴搜 
#include<bits/stdc++.h>
using namespace std;
const int N=400;
int n,p,ans,size[N];//人数，边数，答案，每个点节点个数 
bool vis[N],iscut[N];//判断该点是否被访问，和该点是否被隔离 
vector <int> dep[N];//存每一层的节点 
vector <int> tree[N];//存每个点的子节点 
void docut(int u)
{
	iscut[u]=true;
	for(int i=0;i<tree[u].size();i++)
	{
		int v=tree[u][i];
		docut(v);
	}
}
void uncut(int u)
{
	iscut[u]=false;
	for(int i=0;i<tree[u].size();i++)
	{
		int v=tree[u][i];
		uncut(v);
	}
}
int worksize(int u,int now)//预处理每一个节点的子节点数 
{ 
	vis[u]=true;
	dep[now].push_back(u);//将该节点存入该层 
	for(int i=0;i<tree[u].size();i++)
	{
		int v=tree[u][i];
		size[u]+=worksize(v,now+1); 
	} 
	return size[u];
}
void dfs(int l,int now)//当前层数，没有被隔离的总人数 
{
	for(int i=0;i<dep[l+1].size();i++)
	{
		int v=dep[l+1][i];
		if(iscut[v])	continue;
		docut(v);//将该点隔离 
		dfs(l+1,now-size[v]);//递归循环下一层 
		uncut(v);//回溯 
	}
	ans=min(ans,now);//在dfs中找没有被隔离总人数的最小值即为最优解 
}
int main()
{
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	scanf("%d%d", &n, &p);
	ans=n;
	for(int i=1;i<=n;i++)	size[i]=1;
	for(int i=0;i<p;i++)
	{
		int x,y;
		scanf("%d%d", &x, &y);
		if(x>y)	swap(x,y);//???
		tree[x].push_back(y);
	} 
	worksize(1,1); 
	dfs(1,n); 
	printf("%d", ans);
	return 0;
}