题目链接：P1041 传染病控制
题解：
这个题目是看别人的博客做出来的，其实挺不错的一个题目，考察的东西挺多的，
一个dfs可以处理5个东西：
1、找出父亲
2、找出深度
3、每一层的节点，存进Vector里。
4、更新最大深度
5、找出子树的大小
然后再设定一个Find，找父节点。
只要能找到1，说明感染了，否则说明这个节点已经在之前的操作中切断过。
真的不错的一道题。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 305; 4 vector<int>G[N]; 5 vector<int>V[N]; 6 int Sz[N],dep[N],Pre[N]; 7 int n,m,p,ans,Mx_dep; 8 bool F[N]; 9 bool Find(int x){ 10 if( x == 1 ) return false; 11 if( F[x] == 1 ) return true; 12 else return Find(Pre[x]); 13 } 14 void Build(int Now , int Father ){ 15 Pre[Now] = Father; //父节点 16 dep[Now] = dep[Father] + 1 ; //深度 17 V[dep[Now]].push_back(Now); //每一层有什么元素 18 Mx_dep = max( Mx_dep , dep[Now] );//求出最深深度 19 Sz[Now] = 1 ; //递归求出子树大小 20 for( auto To : G[Now] ){ 21 if( To == Father ) continue; 22 Build( To , Now ); 23 Sz[Now] += Sz[To]; 24 } 25 } 26 void dfs(int depth,int tot ){ 27 if( depth == Mx_dep + 1 ) 28 return ; 29 for( auto To : V[depth] ){ 30 if( Find(To) ) continue; //直接被感染 31 F[To] = 1 ; //尝试切断 32 ans = max( ans , tot + Sz[To] ) ; 33 dfs(depth+1,tot + Sz[To] ); 34 F[To] = 0; //恢复原状 35 } 36 } 37 int main() 38 { 39 scanf("%d%d",&n,&p); 40 for( int i=0,u,v ; i<p ; i++ ){ 41 scanf("%d%d",&u,&v); 42 G[u].push_back(v); 43 G[v].push_back(u); 44 } 45 Build(1,0); 46 dfs(2,0); 47 printf("%d\n",n-ans); 48 return 0; 49 } 50 /* 51 52 7 6 53 1 2 54 1 3 55 2 4 56 2 5 57 3 6 58 3 7 59 60 3 61 */
