作业royal解题报告

1、问题描述：“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室的一个成员来管理。他的国家有 n 个城市，为 1.n。一些城市之间有道路相意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散，每个省至少要有B 个城市，为了能有效的管理，每个省最多只有 3B 个城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省省会）都必须属于该省。经过的道的城市（除了最后一个城市，即该省一个城市可以作为多个省的省会。聪明的你快帮帮这个国王吧！输入文件：第一行包含两个数 N，B（1=N=1000, 1 = B = N）。接

2、下来 N1 行，每行描述一条边，包含两个数，即这条边连接的两个城市的输出文件：。如果国王的要求，输出 0。否则第一行输出数 K，表示你给出的划分方案中省的个数，为 1.K。第二行输出 N 个数，第 I 个数表示为 I的城市属于的省的，第三行输出K 个数，表示这K 个省的省会的城市，如果有多种方案，你可以输出任意一种。分析：问题大意就是，给定一个无向图（实际上是一棵树），要你将这个无向图划分成若干个连通的子图，使得每个子图中结点数处于B，3B内。比较直观的思路是用构造来做，所以，不难得出下面的算法：可以往这方面想。利用递归和贪心的输入的图恰好有N-1 条边，因此根据输入数据构造出一个棵树如果当前

3、还没有划分的点不超过 3B 个，将它们划为一个省，根结点为省会。否则转（3）不超过 3B 个点，直接将它们划分为一个省（3）设当前要从以 I 为根的果存在 J，使得以 J 为根的中划分出省中划分出一个省。设 I 的一个儿子点为 J。如结点数不小于 B，则转为考虑从以 J 为根的以 J 为根的结点树不小于 B 个，递归考虑该的划分方案如果不存在这样的 J，那么依次加入以 I 的儿子结点为根的进入 P 集合，直到 P 中元素的个数不小于 B，将 P 中点划分为一个省，省会为 I。并将划分出的城市从树中去掉，并转（2）依次并入 I 的，发现前 3总结点数超过 B，将棵它们划分成一个省，设 I 为省会

4、。下面给出该算法的简要证明。首先要明确的是省会的划分是一定满足条件的，证明很容易，在此略去。现在要证明的是一定可以得到若干个城市数保持在 N 到 3N 的省。显然，如果当前划分的省是从（3）得到的，那么这次划分前，当前还没有被划分的城市至少有 3N+1 个，然而根据（3）的划分规则，不难证明其划分出的省包含的城市数属于N，2N-2，因此，本次划分后，至少下N+3 个城市，所以通过这样不断的划分，一定可以得到满足条件的划分方案。算法采用递归实现，简洁而高效，具体方法可以参见程序。参考程序：$r-,s-,q- const infnsoutfns maxntype tgvar g=:royal.in

5、;royal.out; 1000;array1 array1 array1array1.maxn maxn maxnmaxnofof of ofeger;tg;eger;tot, donen, m,fa,son,sum,num,centerteger;procedurevar i, x, begininit;y输入过程:eger;assign(input,reset(input);infns);readln(n, m);for i :=1 to n - 1 do beginreadln(x, y); inc(totx); inc(toty); end;for i :=1 to n getmem

6、(gi,toti :=0; end;reset(input); readln(n, m);for i :=1 to ndo beginsizeof(eger) * toti);- 1 do beginreadln(x, y); inc(totx); gxtotxinc(toty); gytoty end;close(input);end;:=y;:=x;procedure maketree(i :eger);根据输入的图构造出一棵树var j, k beginsoni :=1;:eger;for k :=1 to toti do begin j :=gik;if j fai then begi

7、nfaj :=i; maketree(j); inc(soni, sonj); end;end;end;procedure var j, k begindoneicolor(i:eger);:将已经划分到省里面的点标号eger;:=true;numi :=t; soni :=0; inc(sumt);for k :=1 to toti do beginj :=gik;if not donej end;end;and (j fai) then color(j);procedure work(i :eger); 步骤 3 执行过程eger;var j, kbegin:for k :=1 to to

8、ti do begin j :=gik;if not donej and (j fai) and (sonj m) work(j); dec(soni, sumt); exit;end; end;for k :=1 to toti do begin j :=gik;if not donej and (j fai) then begincolor(j);thenbegin步骤 3 的情况 1if sumt = m then begin步骤 3 的情况 2dec(soni, sumt); centert :=i; exit; end;end; end;end;procedure solve; var ibegin:eger;fillchar(done, sizeof(done), false);while son1 3 * m do begin 执行步骤 3inc(t);end;work(1);i1inc(t); 0 then begin 执行步骤 2color(1); centert :=1;end;end;procedure out; 输出过程var ibegin:eger;assign(output, outfns);rewrite(output);wri