NOIP2003传染病控制的满分思路+程序

用搜索。
1.输入边信息，构建有向树
设gl[i]为顶点i的儿子数。
g[i,j]为顶点i的第j个儿子序号（1≤i≤n，1≤j≤gl[i]）。
f[i]为顶点i的周期。
ans为被感染的最少人数，now为当前被感染的人数。
按照下述方式输入p条边的信息：
read(n,m); {读顶点数和边数}
fillchar(gl,sizeof(gl),0); {顶点的度序列初始化}
for i:=1 to m do {输入每一条边的信息}
begin
read(x,y); {读第i条边的两个端点}
inc(gl[x]);g[x,gl[x]]:=y; {顶点x的度+1，x的新增边的另一端点为y}
inc(gl[y]);g[y,gl[y]]:=x; {顶点y的度+1，y的新增边的另一端点为x}
end;{for}
由于输入信息中并没有给出各条边的连接情况，因此必须从顶点1出发构造有向树。构造方法如下：
procedure maketree(k:integer); {从根k出发，构造树}
var
i,j,t:integer;
begin
for i:=1 to gl[k] do {枚举顶点k的每一个儿子}
begin
t:=g[k,i];
for j:=1 to gl[t] do {删除顶点k的第i个儿子指向顶点k的有向边}
if g[t,j]=k then break;
g[t,j]:=g[t,gl[t]];
dec(gl[t]); {从顶点k的第i个儿子出发，继续递归}
maketree(t);
end;{for}
end;{maketree}
在主程序中递归调用maketree(1)，便可以得到有向树g。
2.递归计算被感染的最少人数
现采取搜索的办法，在每个周期开始的时候，枚举前一个周期感染病毒的结点的子节点，断开该节点与父节点的边。
状态（now，f，k）：now为当前被感染的人数，f为每个顶点所在的周期，k为当前周期。k设为值参，now和f设为全局变量。
边界条件（now＞ans）：若当前被感染的人数已超过最小值，则回溯；否则计算k周期内的每一个顶点的儿子数，累计被感染人数now。
搜索范围（1≤i≤n）：搜索处于k+1周期内的每一个顶点（即f[i]=k+1），切断父顶点通向它的传播途径，递归k+1个周期。
由此得出递归程序：
procedure search(k:integer); {搜索在第k个周期中被切断的传播途径}
var
i,j:integer;
found:boolean; {存在标志}
begin
if now>ans then exit; {若当前被感染的人数已超过最小值，则回溯}
found:=false; {未发现被感染的顶点}
for i:=1 to n do {枚举在周期k被感染的顶点}
if f[i]=k then {若顶点i处于周期k，则枚举顶点i的每一个儿子}
for j:=1 to gl[i] do
begin
f[g[i,j]]:=k+1; {顶点i的第j个儿子处于k+1周期}
inc(now); {被感染的人数+1}
found:=true; {发现处于周期k+1的顶点}
end;{for}
dec(now);
for i:=1 to n do
if f[i]=k+1 then {通向顶点i的传播途径被切断}
begin
f[i]:=0;
search(k+1); {递归周期k+1}
f[i]:=k+1;
end;{then}
inc(now); {恢复递归前的now和f}
for i:=1 to n do
if f[i]=k+1 then
begin
f[i]:=0;dec(now);
end;
if (not found) and (now 数最少，则记下}
end;{search}
显然，主程序在根据输入信息构造有向树后，设顶点1处于周期1且被感染（f[i]:=1;now:=1;fillchar(f,sizeof(f),0);f[1]:=1），被感染的最少人数ans初始化为500。然后递归调用search(1)，得出的ans即为问题的解。