跳至正文
题库4148
#4148

传染病控制

查看题目操作

传染病控制

题目描述

近来,一种新的传染病肆虐全球。蓬莱国也发现 了零星感染者,为防止该病在蓬莱国大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完全认识这种传染病,难以准确判别病毒 携带者,更没有研制出疫苗以保护易感人群。于是,蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO(世界卫生组织)以及全球各国科研部门的努力,这种新兴传染病的传播途径和控制方法已经研究消楚,剩下的任务就是由你协助蓬莱国疾控中心制定一个有 效的控制办法。 研究表明,这种传染病的传播具有两种很特殊的性质;  第一是它的传播途径是树型的,一个人X只可能被某个特定的人Y感染,只要Y不得病,或者是XY之间的传播途径被切断,则X就不会得病。  第二是,这种疾病的传播有周期性,在一个疾病传播周期之内,传染病将只会感染一代患者,而不会再传播给下一代。  这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经得到了国内部分易感人群的潜在传播途径图(一棵树)。但是,麻烦还没有结束。由于蓬莱国疾控中 心人手不够,同时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而没有被控制的传播途径就会引起更多的易感人群被感染(也 就是与当前已经被感染的人有传播途径相连,且连接途径没有被切断的人群)。当不可能有健康人被感染时,疾病就中止传播。所以,蓬莱国疾控中心要制定出一个 切断传播途径的顺序,以使尽量少的人被感染。你的程序要针对给定的树,找出合适的切断顺序。

输入格式

的第一行是两个整数n(1≤n≤300)和p。接下来p行,每一行有两个整数i和j,表示节点i和j间有边相连(意即,第i人和第j人之间有传播途径相连,注意:可能是i到j也可能是j到i)。其中节点1是已经被感染的患者。  对于给定的输入数据,如果不切断任何传播途径,则所有人都会感染。

输出格式

只有一行,输出总共被感染的人数。

样例

200 199
2 1
3 2
4 3
5 4
6 4
7 4
8 3
9 3
10 9
11 9
12 11
13 11
14 9
15 9
16 2
17 16
18 17
19 17
20 16
21 20
22 16
23 22
24 2
25 24
26 25
27 24
28 27
29 27
30 27
31 2
32 31
33 32
34 32
35 32
36 35
37 35
38 32
39 31
40 39
41 40
42 40
43 40
44 39
45 44
46 1
47 46
48 47
49 48
50 49
51 49
52 49
53 48
54 53
55 47
56 55
57 55
58 57
59 47
60 59
61 60
62 59
63 62
64 46
65 64
66 65
67 65
68 67
69 64
70 69
71 69
72 64
73 72
74 72
75 64
76 75
77 75
78 46
79 78
80 79
81 80
82 81
83 80
84 80
85 84
86 79
87 86
88 86
89 78
90 89
91 90
92 90
93 89
94 93
95 89
96 95
97 1
98 97
99 98
100 99
101 98
102 101
103 98
104 98
105 104
106 104
107 106
108 97
109 108
110 109
111 109
112 111
113 109
114 108
115 114
116 115
117 114
118 114
119 118
120 118
121 108
122 121
123 97
124 123
125 124
126 125
127 124
128 127
129 127
130 127
131 127
132 123
133 132
134 133
135 134
136 133
137 133
138 137
139 137
140 132
141 140
142 140
143 97
144 143
145 144
146 144
147 146
148 144
149 148
150 143
151 150
152 150
153 1
154 153
155 154
156 155
157 156
158 155
159 158
160 158
161 155
162 161
163 161
164 154
165 164
166 165
167 164
168 167
169 164
170 169
171 153
172 171
173 171
174 173
175 174
176 173
177 176
178 171
179 178
180 178
181 171
182 181
183 181
184 181
185 181
186 153
187 186
188 187
189 188
190 187
191 187
192 186
193 192
194 192
195 192
196 186
197 196
198 196
199 198
200 196
111

配图

配图

来源

蓝桥杯 算法提高