[ZJ][DFS] d842. NOIP2003 4.传染病控制
內容 ：
近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国
大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完
全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，
蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫
生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究
消楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。
研究表明，这种传染病的传播具有两种很特殊的性质；
第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不
得病，或者是XY之间的传播途径被切断，则X就不会得病。
第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一
代患者，而不会再传播给下一代。
这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群
的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同
时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而
没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有
传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止
传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。
你的程序要针对给定的树，找出合适的切断顺序。
輸入說明
：
输入格式的第一行是两个整数n（1≤n≤300）和p。接下来p行，每一行有两个整数i
和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。其中节点
1是已经被感染的患者。
輸出說明
：
只有一行，输出总共被感染的人数。
範例輸入 ：
7 6 1 2 1 3 2 4 2 5 3 6 3 7
範例輸出 ：
3
提示
：
出處
：
其實這題有個很詭異的地方，既然是一棵樹，其實不用給 p，給節點個數就好了。
接著找尋每一層有哪些節點，在每一層窮舉一個節點擋掉，直到某一層沒有任何節點可以繼續傳染。
不剪枝也會過。
/**********************************************************************************/
/* Problem: d842 "NOIP2003 4.传染病控制" from NOIP2003提高组第四题 */
/* Language: C (1271 Bytes) */
/* Result: AC(10ms, 487KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-22 16:02:57 */
/**********************************************************************************/
#include <stdio.h>
int g[305][305], gt[305];
int tg[305][305], tgt[305], p[305];
int used[305];
int layer[305][305], lt[305] = {};
void make_root(int nd, int dep) {
layer[dep][lt[dep]++] = nd;
used[nd] = 1;
int i;
for(i = 0; i < gt[nd]; i++) {
if(used[g[nd][i]] == 0) {
tg[nd][tgt[nd]++] = g[nd][i];
p[g[nd][i]] = nd;
make_root(g[nd][i], dep+1);
}
}
}
int o[305], res = 0xffff;
void dfs(int dep, int sum) {
int i, cnt = 0;
for(i = 0; i < lt[dep]; i++) {
if(o[p[layer[dep][i]]] == 1)
o[layer[dep][i]] = 1;
else
cnt++, o[layer[dep][i]] = 0;
}
if(cnt == 0) {
if(sum < res)
res = sum;
return;
}
if(sum >= res) return;
for(i = 0; i < lt[dep]; i++) {
if(o[layer[dep][i]] == 0) {
o[layer[dep][i]] = 1;
dfs(dep+1, sum+cnt-1);
o[layer[dep][i]] = 0;
}
}
}
int main() {
int n, p, x, y;
scanf("%d %d", &n, &p);
while(p--) {
scanf("%d %d", &x, &y);
g[x][gt[x]++] = y;
g[y][gt[y]++] = x;
}
make_root(1, 1);
dfs(2, 1);
printf("%d\n", res);
return 0;
}