- 题目链接：传染病控制
- 题目思路：
- 第一种思路：贪心，由题意得，本题可以建模为一棵树，在每一层上切断一条边，让被感染的节点数最少。如果我们用一个数组把每个子树所包含的节点数记录下来，在每次切割时切节点数最大的节点，这其实是不对的，下图为HACK数据。
- 第二种思路（正解）：对于切割一条边，我们可以换一种想法，假设当前一层有x,y,z三个节点，我们要切掉x，那么y、z会被感染，那么其实z的子节点可以合并到y上，这样就方便我们爆搜。如下图所示。
根据数据范围，我们可以简单地用邻接矩阵来建树，具体含义见代码。
- 第一种思路：贪心，由题意得，本题可以建模为一棵树，在每一层上切断一条边，让被感染的节点数最少。如果我们用一个数组把每个子树所包含的节点数记录下来，在每次切割时切节点数最大的节点，这其实是不对的，下图为HACK数据。
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
using namespace std;
int sc() {
int xx=0,ff=1; char cch;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-ff; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=xx*10+(cch-48); cch=gc;
}
return xx*ff;
}
int Map[Maxn][Maxn],tree[Maxn][Maxn];
int n,m,ans=INF;
int findroot(int x,int i) { //找相邻节点
if(i==1) return tree[x][2];
return tree[x][1];
}
void dfs(int now,int sum) {
if(sum+tree[now][0]-1>=ans) return ; //剪枝
if(tree[now][0]<=1) { //如果已经是最后一层，取最小值，跳出
ans=min(ans,sum);
return ;
}
for(int i=1; i<=tree[now][0]; i++) { //枚举每一个子节点
int y=tree[now][i];
int root=findroot(now,i); //找相邻节点
int re=tree[root][0]; //记录原节点数，用来回溯
for(int j=1; j<=tree[now][0]; j++) {
int yy=tree[now][j];
if(y!=yy&& yy!=root) {
for(int k=1; k<=tree[yy][0]; k++) //把一个节点的子树转移到另一个节点上
tree[root][++tree[root][0]]=tree[yy][k];
}
}
dfs(root,sum+tree[now][0]-1); //往下爆搜
tree[root][0]=re; //回溯
}
}
void build(int x) {
for(int i=1; i<=n; i++) {
if(Map[x][i]) {
tree[x][++tree[x][0]]=i; //tree数组就不解释了，自行理解。。。
Map[x][i]=Map[i][x]=0;
build(i);
}
}
}
int main() {
n=sc(); m=sc();
for(int i=1; i<=m; i++) {
int x=sc(),y=sc();
Map[x][y]=Map[y][x]=1; //Map数组不解释，自行理解。。。
}
build(1); //建树
dfs(1,1);
printf("%d",ans);
return 0;
}