记录编号	386934	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-03-25 11:10:18	内存使用	0.00 MiB

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN=310;

struct Edge{
	int from;
	int to;
	Edge* prev;
};

Edge E[MAXN];
Edge* head[MAXN];
Edge* top=E;

int n;
int m;
int ans;
int son[MAXN];
int size[MAXN];
int parent[MAXN];

bool visited[MAXN];

queue<int> q;

vector<int> v;

void Initialize();
void Insert(int,int);
void DFS(int);
void BFS(int);

int Main(){
	Initialize();
	DFS(1);
	BFS(1);
	printf("%d\n",ans);
	return 0;
}

void BFS(int root){
	int to;
	q.push(root);
	goto tg;
	do{
		to=0;
		for(vector<int>::iterator iter=v.begin();iter!=v.end();iter++)
			if(size[*iter]*2+(son[*iter]*3)>size[to]*2+(son[to]*3))
				to=*iter;
		for(vector<int>::iterator iter=v.begin();iter!=v.end();iter++)
			if(to!=*iter)
				q.push(*iter);
tg:
		v.clear();
		while(!q.empty()){
			root=q.front();
			q.pop();
			ans++;
			for(Edge* i=head[root];i!=NULL;i=i->prev){
				to=i->to;
				if(to==parent[root])
					continue;
				v.push_back(to);
			}
		}
	}while(!v.empty());
}

void DFS(int root){
	int to;
	size[root]=1;
	for(Edge* i=head[root];i!=NULL;i=i->prev){
		to=i->to;
		if(parent[root]==to)
			continue;
		else{
			son[root]++;
			parent[to]=root;
			DFS(to);
			size[root]+=size[to];
		}
	}
}

inline void Insert(int from,int to){
	top->from=from;
	top->to=to;
	top->prev=head[from];
	head[from]=top;
	top++;
}

void Initialize(){
	int from,to;

	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&from,&to);
		Insert(from,to);
		Insert(to,from);
	}
}

int WORKING=Main();
int main(){;}