null搜索法搜索法null 无论什么类型的试题,只要能归纳出数学模型,我们尽量用解析方法求解。因为一个好的数学模型建立了客观事物间准确的运算关系。运用这个数学模型直接求解是再合适不过的了。当然,这仅是一种可能性,因为并非所有选手都能在竞赛的“一瞬间”把问题
得如此透彻,并非所有给定的问题都能建立数学模型,即便有了数学模型,但解该模型的准确方法也不一定能立即运用现成算法。因此在某些情况下,还得需要通过搜索(列举所有可能情况)来寻求问题的解。
典型的算法:
枚举法
回溯法 回溯法 回溯法 回溯法也是搜索算法中的一种控制策略,但与枚举法不同的是,它是从初始状态出发,运用题目给出的条件、规则,按照深度优秀搜索的顺序扩展所有可能情况,从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 null运用算法框架解题回溯法的优化算法框架算法框架procedure run(当前状态);
var
i:integer;
begin
if 当前状态为边界
then begin
if 当前状态为最佳目标状态 then 记下最优结果;
exit;{回溯}
end;{then}
for i←算符最小值 to 算符最大值 do
begin
算符i作用于当前状态,扩展出一个子状态;
if (子状态满足约束条件) and (子状态满足最优性要求)
then run(子状态);
end;{for}
end;{run}
在应用算法框架解题时应考虑的因素在应用算法框架解题时应考虑的因素⑴定义状态:即如何描述问题求解过程中每一步的状况。为了精简程序,增加可读性,我们一般将参与子结点扩展运算的变量组合成当前状态列入值参,以便回溯时能恢复递归前的状态,重新计算下一条路径;
⑵边界条件:即在什么情况下程序不再递归下去。如果是求满足某个特定条件的一条最佳路径,则当前状态到达边界时并非一定意味着此时就是最佳目标状态。因此还须增加判别最优目标状态的条件;
⑶搜索范围:在当前状态不满足边界条件的情况下,应如何设计算符值的范围。换句话说,如何设定for语句中循环变量的初值和终值。
⑷约束条件和最优性要求:当前扩展出一个子结点后应满足什么条件方可继续递归下去;如果是求满足某个特定条件的一条最佳路径,那么在扩展出某个子状态后是否继续递归搜索下去,不仅取决于子状态是否满足约束条件,而且还取决于子状态是否满足最优性要求。
⑸参与递归运算的参数:将参与递归运算的参数设为递归子程序的值参或局部变量。若这些参数的存储量大(例如数组)且初始值需由主程序传入,为避免内存溢出,则必须将其设为全局变量,且回溯前需恢复其递归前的值。
构造字串构造字串 生成长度为n的字串,其字符从26个英文字母的前p(p≤26)个字母中选取,使得没有相邻的子序列相等。例如p=3,n=5时
‘a b C b a’满足条件
‘a b C b C’不满足条件
输入:n,p
输出:所有满足条件的字串
分析
分析
状态:待扩展的字母序号at。实际上字串s亦参与了递归运算,但是由于该变量的存储量太大,因此我们将s设为全局变量;
边界条件和目标状态:产生了一个满足条件的字串,即at=n+1;
搜索范围:第at位置可填的字母集{'a'.. chr(ord('a')+p-1)};
约束条件:当前字串没有相邻子串相等的情况
var
n,p:integer;{字串长度和可选字母的个数}
tl:longint; { 满足条件的字串数}
ed:char; { 可选字母集中的最大字母}
s:string; {满足条件的字串}
nullprocedure solve(at:integer);{递归扩展第at个字母}
var
ch:char; i:integer;
begin
if at=n+1 {若产生了一个满足条件的字串,则输出,满足条件的字串数+1}
then begin writeln(f,s); inc(tl);exit{回溯}end;{then}
for ch←'a' to ed do {搜索每一个可填字母}
begin
s←s+ch;i←1;{检查当前字串是否符合条件}
while(i<=atdiv2)and(copy(s,length(s)-i+1,i)<>copy(s,length(s)-2*i+1,i)) do inc(i);
nullif i>at div 2 then solve(at+1);{若当前字串符合条件,则递归扩展下一个字母}
delete(s,length(s),1){恢复填前的字串}
end{for}
end;{solve}
begin
readln(n,p);{输入字串长度和前缀长短}
ed←chr(ord('a')+p-1);{计算可选字母集中的最大字母}
s←''; tl←0;{满足条件的字串初始化为空,字串数为0}
solve(1);{从第1个字母开始递归计算所有满足条件的字串}
writeln('Total:',tl);{输出满足条件的字串数}
end.{main}
字串变换字串变换[问题描述]:已知有两个字串A$,B$及一组字串变换的规则:
A1$→B1$
A2$→B2$
………
规则的含义为:在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…..。例如:A$ =‘abcd’ B$=‘xyz’
变换规则为:‘abc’→‘xu’ ‘ud’→‘y’ ‘y’→‘yz’,则此时,A$可以经过一系列的变换变为B$,其变换的过程为:
‘abcd’→‘xud’→‘xy’→‘xyz’
共进行了三次变换,使得A$变换为B$。
[输入]:
A$,B$
A1$ → B1$
A2$ → B2$
变换规则………
所有字符串长度的上限为255。
[输 出]:若在30步(包含30步)以内能将A$变换为B$,则输出最少的变换步数;否则输出‘ERROR!’。
1、分析变换规则1、分析变换规则设规则序列为rule,其中第i条规则为rule[i,1]→rule[i,2];
当前串为now,其中tmp为now的一个待匹配子串。由于匹配过程的由左而右进行的,因此设j为now的指针,即从now的第j个字符开始匹配rule[i,1]。now适用第i条规则的条件是
now中的子串被第i条规则替换后的长度小于255,即
length(now)+length(rule[i,2])-length(rule[i,1])≤255
rule[i,1]是now的一个子串(k=pos(rule[i,1],tmp)≠0)
在使用了第i条规则后,now变换为
now= copy(now,1,j+k-1)+rule[i,2]+copy(now,j+k+length(rule[i,1]),255)
由于now中可能有多个子串被第i条规则替换,因此每替换一次后,为了方便地找出下一个替换位置,我们将当前被替换串前(包括被替换串)的子串删除。 2、使用回溯法计算最少替换次数2、使用回溯法计算最少替换次数 由于原串a、目标串b和规则rule是随机输入的,因此不可能找出直接计算最少替换次数best的数学规律,只能采用回溯搜索的办法。设
状态(need,now):替换次数为need,替换结果为now;
边界条件(need≥best)和目标状态(now=b):替换次数达到或超过目前得出的最小值为边界;已经替换出目标串为目标状态;
搜索范围i:尝试每一条规则,即1≤i≤规则数n;
约束条件(length(now)+length(rule[i,2])-length(rule[i,1])≤255):now中的子串被第i条规则替换后的长度小于255;nullprocedure solve(need;now);{从当前串now出发,递归第need次替换}
var
i,k,j:integer;
tmp:string;
begin
if need>=best then exit;{若到达边界,则回溯}
if now=b then begin{若达到目标状态,则记下替换次数,并回溯}
best←need; exit;
end;{then}
for i←1 to n do {搜索每一条规则}
nullif length(now)+length(rule[i,2])-length(rule[i,1])<=255
then begin{若使用了第i条规则后,串长不会超过上限}
j←0; tmp←now;{匹配指针初始化和待匹配子串初始化}
k←pos(rule[i,1],tmp); {尝试第i条规则}
while k>0 do {反复在tmp 中寻找子串rule[i,1]}
begin {递归下一次替换}
solve(need+1,copy(now,1,j+k-1)+rule[i,2]+copy(now,j+k+length(rule[i,1]),255));
delete(tmp,1,k);{将当前被替换串前(包括被替换串)的子串删除}
j←j+k;{右移匹配指针}
k←pos(rule[i,1],tmp); {继续尝试第i条规则}
end;{while}
end;{then}
end;{ solve }
null由此得出主程序:
读入初始串a和目标串b;
读入替换规则rule;
best←31;{设定替换次数的上限}
solve(0,a);{回溯搜索最少的替换次数}
if best<=30{输出最少替换次数}
then writeln(best)
else writeln('ERROR!');
、
优化回溯法
优化回溯法
优化方法1:递归前预处理 优化方法2:记忆化搜索优化方法3:寻找解析式优化方法1:递归前的预处理优化方法1:递归前的预处理 如果搜索对象是通过某种运算直接得出其结果的,那么搜索前一般需进行预处理
①通过相应运算将所有搜索对象的计算结果置入常量表,搜索过程中只要将当前搜索对象的结果值从常量表取出即可。这样可以显著改善搜索效率。否则,在搜索过程中每遇到这些对象都要计算,则会产生大量的重复运算。
②为减少搜索量,预先确定某些对象的初始值
③构造初始解,以便缩小搜索范围,“苛刻”约束条件
回溯法的优化方法1——预处理回溯法的优化方法1——预处理因式分解
将大于1的自然数N进行因式分解,满足N=a1*a2*a3...am 且1
方案。
输入: N由键盘输入
输出:第1行至第M行输出所有的M种方案(顺序不限),第M+1行输出方案总数M。
例如输入 N=12,输出:
12=2*6
12=2*2*3
12=3*4
M=3
算法分析算法分析1、 构造因子表
如果完全盲目地搜索所有候选解,其代价相当大。为了改善搜索效率,我们不妨先将n分解成两个因子相乘的所有可能形式:
n=n1*n2
将所有不同的因子按递增顺序存入a表:
k←0; {a表的元素初始化}
for i:=2 to sqrt(n) do{n试除2,‥ sqrt(n) ,产生一半因子}
if n mod i=0 then begin k←k+1;ak←i;end; {then}
p←k; k←2*k;
if (aΡ)2=n then k←k-1;{计算a表的因子数}
for i:=1 to P do ak+1-i←n/ai;{由n分别除以a1‥ak,产生另一半因子}
显然,因式分解的因子在a表中。问题是分解过程中a表的因子可能会在因式中重复出现。在这种情况下应怎么办?2、 回溯搜索分解方案2、 回溯搜索分解方案设目前分解的因式为n=b1*b2*…*bh*n’,其中n’为尾因子。b1…bh已从a表中选取了a1…aj-1,n’尚待分解出不同因子aj…ak。
①结点定义:我们将a表中待分解的因子aj作为状态,a表指针作为算符;
②边界和目标状态的条件:若从因子表中分解出的因子数h>0,则产生一个分解方案n=b1*‥*bh*n’
③ 搜索范围:目前因式中尚待分解出因子ai.显然 j≤i≤k
④ 约束条件: ((n’div ai )≥ai)and(n’mod ai=0)
注:若不能满足有序性要求( n’div ai )
0 then 输出第t个方案为n=b1*b2*…*bh*n’;
for i:=j to k do {试分解aj…ak}
if n’div aia,则说明a不可能分解出比prime[i]大的素数了,a本身为素数。由于prime[i]表的最大素数接近10000,其平方远大于xi的上限5000000*19,因此是一个比较可行的方法:
function check(a:longint):boolean;{判断a是否是素数}
begin
check←true;{素数标志初始化}
for i←1 to tot do begin {搜索素数表}
if prime[i]*prime[i]>a then exit;{若超出搜索范围的上限,则说明a是素数,返回true}
if a mod prime[i]=0
then begin check←false;exit;end;{then}
end;{for}
end;{ check }
2、递归搜索方案数
2、递归搜索方案数
由于数列是随机和无序的,因此只能通过搜索的办法求解。设
状态(left,now,all):目前组合为all,还需要从xnow‥xn中选出left个数;
约束条件(left≤n-now+1):xnow‥xn中数的个数大于等于left;
边界条件((left=0) and (now=n+1))和目标状态(check(all)=true):从x1‥xn中选出k个数为边界。在这种情况下,若k个数的和为素数,则满足条件的种数+1。到达边界后,应回溯;
搜索范围为两种选择:
当前组合不选xnow,递归计算子状态(left,now+1,all);
在还有数需要选的情况下(left>0),xnow选入组合,递归计算子状态(left-1,now+1,all+list[now]);
由此得出子程序nullProcedure solve(left,now,all:longint);{递归计算选数情况}
begin
if (left>n-now+1) then exit;{ 若xnow‥xn中不足left个数,则回溯}
if (left=0) and (now=n+1){若从x1‥xn中选出了k个数}
then begin
if check(all) then inc(ans);{若k个数的和为素数,则满足条件的种数+1}
exit; {回溯}
end;{then}
solve(left,now+1,all);{当前组合不选xnow,递归计算子状态}
if left>0 {在还有数需要选的情况下,xnow选入组合,递归计算子状态}
then solve(left-1,now+1,all+list[now]);
end;{ solve}
显然,递归调用solve(k,1,0)后得出的ans即为问题的解。
交易
交易
在n个城市间连接了m条道路,连接每条道路的两个城市间可进行一次交易,产生一定的收益。请设计一个能产生最大经济效益的交易方案。
输入:
城市数n(1≤n≤100)和道路数m(m>0);
以下有m行,每行为“i j v”表示城市i和城市j之间进行一次交易的收益为v;
输出:
n个整数。与城市i进行一次交易的城市序号为其中第i个整数;如果没有城市与城市i进行交易,则第i个整数为0。数据类型数据类型var
n,m,i,j,k,n0,a,b:integer;
g:array[1..max,1..max]of real;{无向有权图}
bt,w,aw:real;{ bt为最大经济效益}
hv:array[1..max]of real;{ 每个城市的交易量}
vt:array[1..max]of boolean;{未交易标志}
ans,bans:array[1..max]of byte;{ bans为最佳交易方案,其中bans[i]为与城市i进行一次交易的城市序号;ans 为当前交易方案}初始化初始化4、计算最大经济效益bt和交易方案bans的初始值 4、计算最大经济效益bt和交易方案bans的初始值 inc(n);
for i:=1 to n-1 do g[i,n]:=0;
bt:=0;{ 最大经济效益初始化}
fillchar(vt,sizeof(vt),0);
fillchar(bans,sizeof(bans),0);{每个城市的交易对象初始化}
for i:=1 to n-1 do{搜索每一个未交易城市i}
if not vt[i]
then begin
k:=0;{在与城市i相连的未交易城市里选择交易量最大的城市k}
for j:=i+1 to n do
if not vt[j] and ((k=0) or (g[i,j]>g[i,k]))then k:=j;
if (k<>0) and (g[i,k]>=0){若城市k存在,则设定城市i与城市k交易,交易量记入经济效益}
then begin
bt:=bt+g[i,k];
bans[i]:=k; bans[k]:=i; vt[k]:=true
end
end;递归计算最大经济效益和交易方案递归计算最大经济效益和交易方案procedure search(nw:integer;lg:real);{从nw城市和交易量lg出发,递归计算最大经济效益bt和交易方案bans}
var
i:integer;
begin
if lg<=bt then exit;
if vt[nw]{若城市nw已确定交易对象,则递归}
then begin search(nw+1,lg); exit end;
if nw=n+1{若每个城市的交易对象已确定,则记下经济效益和交易表}
then begin bt:=lg;bans:=ans;exit end;
for i:=nw+1 to n do{在未交易的城市中搜索与城市nw相连的城市i}
if (i=n) or not vt[i] and (g[nw,i]>=0)
then begin
ans[nw]:=i; ans[i]:=nw; vt[i]:=true;{城市i和城市nw交易,并递归}
search(nw+1,lg-hv[nw]-hv[i]+g[nw,i]);
ans[nw]:=0; ans[i]:=0; vt[i]:=false{恢复递归前的状态}
end
end;主程序主程序输入信息,进行递归前的初始化;
fillchar(vt,sizeof(vt),0);{所有城市未交易}
fillchar(ans,sizeof(ans),0);{当前交易标未空}
search(1,aw);
输出最大经济效益bt和交易方案bans;回溯法的优化方法 2—记忆化搜索回溯法的优化方法 2—记忆化搜索 如果解答树中存在一些性质相同的子树,那么,只要我们知道了其中一棵子树的性质,就可以根据这个信息,导出其它子树的性质。这就是自顶向下记忆化搜索的基本思想。
序关系计数问题
序关系计数问题
用关系’<’和’=’将3个数a、b和C依次排列有13种不同的关系:
a规定 等号前面的大写字母在ASCII表中的序号,必须比等号后面的字母序号小。
null状态(Step,First,Can):其中Step表示当前确定第Step个关系符号;First表示当前大写字母中最小字母的序号;Can是一个集合,集合中的元素是还可以使用的大写字母序号
边界条件(step=n):即确定了最后关系符号
搜索范围(First≤i≤n):枚举当前大写字母的序号
约束条件(i in Can):序号为i的大写字母可以使用
算法1:
procedure Count(Step,First,Can); {从当前状态出发,递归计算序关系表达式数}
begin
if Step=n then begin {若确定了最后一个关系符号,则输出统计结果}
for i←First to n do if i in Can then Inc(Total);
Exit {回溯}
end;{then}
for i←First to n do {枚举当前的大写字母}
if i in Can then begin {序号为i的大写字母可以使用}
Count(Step+1,i+1,Can-[i]);{添等于号}
Count(Step+1,1,Can-[i]) {添小于号}
End{then}
end;{ Count}主程序调用Count(1,1,[1..n])后,Total的值就是结果。该算法的时间复杂度是W(n!)
null2、粗略利用信息
若已经确定了前k个数,并且下一个关系符号是小于号,这时所能产生的序关系数就是剩下的n-k个数所能产生的序关系数。
设i个数共有F[i]种不同的序关系,那么,由上面的讨论可知,在算法1中,调用一次Count(Step+1,1,Can-[i])之后,Total的增量应该是F[n-Step]。这个值可以在第一次调用Count(Step+1,1,Can-[i])时求出。而一旦知道了F[n-Step]的值,就可以用Total←Total+F[n-Step] 代替调用Count(Step+1,1,Can-[i])
nullprocedure Count(Step,First,Can); {Step,First,Can的含义同算法1}
begin
if Step=n then begin {若确定了最后一个关系符号,则输出统计结果}
for i←First to n do if i in Can then Inc(Total);Exit {回溯}
end;{then}
for i←First to n do {枚举当前的大写字母}
if i in Can {序号为i的大写字母可以使用}
then begin
Count(Step+1,i+1,Can-[i]);{添等于号}
if F[n-Step]=-1
then begin ( 第一次调用}
F[n-Step] ←Total;Count(Step+1,1,Can-[i]); {添小于号}
F[n-Step] ←Total-F[n-Step] {F[n-Step]=Total的增量}
end {then}
else Total←Total+F[n-Step] {F[n-Step]已经求出}
end{then}
end;{count}
该算法实质上就是自顶向下记忆化方式的搜索,它的时间复杂度为W(2n)。 null3、充分利用信息
在搜索的过程中,如果确定在第k个大写字母之后添加第一个小于号,则可得到下面两条信息:
第一条信息:前k个大写字母都是用等号连接的。前半部分将产生的序关系数,就是n个物体中取k个的组合数
第二条信息:在此基础上继续搜索,将产生F[n-k]个序关系表达式。
这样,我们可以得到F[n] 的递推关系式:
采用上述
计算F[n]的算法记为算法3,它的时间复杂度是W(n2)。
nullvar
Total:Comp;{答案}
F:array[0..maxn] of Comp;{F[i]为i个数的序关系表达式个数}
i,j:Integer;
x:Comp;
begin
FillChar(F,Sizeof(F),0);{F初始化}
F[0] ←1;
for i←1 to n do begin{递推F数组}
F[i] ←0;x←1;
for j←1 to i do begin x←x*(i-j+1)/j;F[i] ←F[i]+x*F[i-j] End{for}{计算F[i]}
end;{for}
writeln(F[n]); {输出结果}
end;{main}
算法3充分利用信息,通过两重循环的递推计算F[n],将时间复杂度降到W(n2),实现了程序的最优性要求。 优化方法 3—寻找解析式和贪心策略优化方法 3—寻找解析式和贪心策略 在充分利用信息的基础上建立数学模型和贪心策略,将搜索解题优化为直接递推解题。null栈
【问题背景】栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。
【问题描述】
null宁宁考虑的是这样一个问题:一个操作数序列,从1,2,一直到n(图示为1到3的情况),栈A的深度大于n。
现在可以进行两种操作,
1.将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作)
2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作)
123使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由1 2 3生成序列2 3 1的过程。(原始状态如上图所示)你的程序将对给定的n,计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。
null【输入
】输入文件只含一个整数n(1≤n≤18)
【输出格式】输出文件只有一行,即可能输出序列的总数目
第一种解法——回溯法
设total为输出序列的总数目;输出序列的尾指针为l,堆栈的栈首指针为tp,当前准备入栈的操作数为r。我们采用回溯法计算输出序列的总数目。
状态(tp,l,r):栈首指针,输出序列指针,当前准备入栈的操作数;
边界条件和目标(r=n+1):所有操作数入栈,即得到一个输出序列。此时,total+1,回溯;
搜索范围:有两种操作
栈非空(tp<>0),则栈顶元素进入输出序列,递归子状态(tp-1,l+1,r);
操作数序列的首元素入栈, 递归子状态(tp+1,l,r+1)。
nullprocedure search(tp,l,r);
begin
if r=n+1{若得到一个输出序列,则输出序列的总数目+1,回溯}
then begin total:= total+1;exit{回溯} end;{then}
if tp<>0{若栈非空,则栈顶元素进入输出序列,递归}
then search(tp-1,l+1,r);
search(tp+1,l,r+1); {操作数序列的首元素入栈, 递归}
end;{ search }
主程序调用search(0,0,1)后得出的total即为输出序列的总数目。 第二种解法——计算Catalan数 第二种解法——计算Catalan数 对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。
在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。
null不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。显然,不符合要求的方案数为c(2n,n+1)。由此得出
输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。
null设f[i,j]为 。我们按照下述方法计算Catalan数
read(n);{输入操作数的个数}
fillchar(f,sizeof(f),0);
f[1,1]:=1;{ =1}
for i:=2 to 2*n do{递推 }
begin
f[i,1]:=i;
for j:=2 to n do f[i,j]:=f[i-1,j]+f[i-1,j-1];
end;{for}
writeln(f[2*n,n] div (n+1));{输出输出序列的总数目(即Catalan数)}
传染病控制
传染病控制 【问题背景】近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO(世界卫生组织)以及全球各国科研部门的努力,这种新兴传染病的传播途径和控制方法已经研究消楚,剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。
【问题描述】研究表明,这种传染病的传播具有两种很特殊的性质;
第一是它的传播途径是树型的,一个人X只可能被某个特定的人Y感染,只要Y不得病,或者是XY之间的传播途径被切断,则X就不会得病。null 第二是,这种疾病的传播有周期性,在一个疾病传播周期之内,传染病将只会感染一代患者,而不会再传播给下一代。
这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经得到了国内部分易感人群的潜在传播途径图(一棵树)。但是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而没有被控制的传播途径就会引起更多的易感人群被感染(也就是与当前已经被感染的人有传播途径相连,且连接途径没有被切断的人群)。当不可能有健康人被感染时,疾病就中止传播。所以,蓬莱国疾控中心要制定出一个切断传播途径的顺序,以使尽量少的人被感染。你的程序要针对给定的树,找出合适的切断顺序。
【输入格式】输入格式的第一行是两个整数n(1≤n≤300)和p。接下来p行,每一行有两个整数i和j,表示节点i和j间有边相连(意即,第i人和第j人之间有传播途径相连)。其中节点1是已经被感染的患者。
【输出格式】只有一行,输出总共被感染的人数。
解法1——搜索 解法1——搜索 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}
null由于输入信息中并没有给出各条边的连接情况,因此必须从顶点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]);
maketree(t);{从顶点k的第I个儿子出发,继续递归}
end;{for}
end;{ maketree }
在主程序中递归调用maketree(1),便可以得到有向树g。 2、递归计算被感染的最少人数
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周期;
nullprocedure 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;{顶点I的第j个儿子处于k+1周期,被感染的人数+1}
begin f[g[i,j]]:=k+1; found:=true; inc(now)end;{for}
dec(now);
for i:=1 to n do
if f[i]=k+1{通向顶点i的传播途径被切断}
thenbegin 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
= 0) and (S + doors[N] <= L){若火车停靠在月台中间,则计算火车停靠s位置后所有人移动的距离和,并调整最大距离和}
then begin
dist := calc(S);
if dist > answer
then begin answer := dist; posi := S; end;