记录编号	182914	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.284 s
提交时间	2015-08-29 11:40:47	内存使用	4.14 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
int tim[maxn],n,ans=1e6,num;
int v[maxn][maxn];
bool f[maxn][maxn];

void Deleteedge(int x){
	int pos,now;
	for (int i=1;i<=v[x][0];++i){
		now=v[x][i];
		for (int j=1;j<=v[now][0];++j)
		   if (v[now][j]==x){
				v[now][j]=v[now][v[now][0]];
				v[now][0]--; Deleteedge(now);
				break;
		   }
	}
}

void ss(int x){
	bool F=0;if (num>=ans) return ;
	for (int i=1;i<=n;++i)
	   if (tim[i]==x){
		  for (int j=1;j<=v[i][0];++j) {
			 num++; F=1;
			 tim[v[i][j]]=x+1;
		  }
	   }
	num--;
	for (int i=1;i<=n;++i)
	   if (tim[i]==x+1) {tim[i]=0;ss(x+1);tim[i]=x+1;}
	num++;
	for (int i=1;i<=n;++i) if (tim[i]==x+1){num--;tim[i]=0;}
	if (!F) ans=min(ans,num);
}

int main()
{
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	int x,y,p;
	scanf("%d %d",&n,&p); 
	for (int i=1;i<=p;++i){
		scanf("%d %d",&x,&y);
		v[x][++v[x][0]]=y;
		v[y][++v[y][0]]=x;
	}
	memset(tim,0,sizeof(tim));
	Deleteedge(1);num=1;
	tim[1]=1;//!!!!!!!!!!!
	ss(1);
	printf("%d",ans);
	return 0;
}