【NOIP2003】传染病控制

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m,ans;
 4 int vis[310],size[310];
 5 vector<int> a[310];
 6 vector<int> t[310];
 7 vector<int> c[310];
 8 queue<pair<int,int> > q;
 9 void change() {
10     q.push(make_pair(1,0));
11     vis[1]=1;
12     while(!q.empty()) {
13         int now=q.front().first;
14         int num=q.front().second;
15         q.pop();
16         t[num].push_back(now);
17         for(int i=0;i<a[now].size();i++)
18             if(!vis[a[now][i]]) {
19                 q.push(make_pair(a[now][i],num+1));
20                 vis[a[now][i]]=1;
21             }
22     }
23 }
24 int calc(int now,int fa) {
25     for(int i=0;i<a[now].size();i++)
26         if(a[now][i]!=fa) {
27             c[now].push_back(a[now][i]);
28             size[now]+=calc(a[now][i],now);
29         }
30     return size[now]+=1;
31 }
32 void tag(int now,int val) {
33     vis[now]=val;
34     for(int i=0;i<c[now].size();i++)
35         tag(c[now][i],val);
36 }
37 void dfs(int s,int sum) {
38     ans=max(ans,sum);
39     for(int i=0;i<t[s].size();i++) {
40         if(!vis[t[s][i]]) {
41             sum+=size[t[s][i]];
42             tag(t[s][i],1);
43             dfs(s+1,sum);
44             sum-=size[t[s][i]];
45             tag(t[s][i],0);
46         }
47     }
48 }
49 int main() {
50     scanf("%d%d",&n,&m);
51     for(int i=1;i<=m;i++) {
52         int x,y;
53         scanf("%d%d",&x,&y);
54         a[x].push_back(y);
55         a[y].push_back(x);
56     }
57     change();
58     calc(1,0);
59     memset(vis,0,sizeof(vis));
60     dfs(1,0);
61     printf("%d\n",n-ans);
62     return 0;
63 }