冬令营作业wc sgu122解题报告

1、Sgu122 解题浙江省杭州第二中学题目大意给一张 n 个节点简单无向图，每个点的度大于等于(n+1) div 2，找一条 hamilton 回路分析因为每个点的度大于等于(n+1) div 2，那么从任意两点出发必然有两条边连到同一个点，它们连通。所以该图连通。用构造的。首先对于图中一个环 R。如果 R 的长度小于n，由于图是连通的，该环上必然有一个点u 连到环外的某点 v，这样从环外的点 v 开始，走到 u，再沿着环走一圈，就可以得到一条链 L，L 的长度比 R 大 1，L 的两端不断进行扩展，直到无法扩展，此时从 L 的两个端点开始没有连向 L 以外某点的边。设 L 有 p 个节点，p

2、= n ，p 的两个端点分别 x,y，x 和 y 的度和大于等于 n，也就是说与 x、y 连接的边超过 n 条，这些边都连向 L 中的 p-2个点，那么 L 上必然存在两个相邻的点，靠近 x 的那个点 a 连向 y 有边，靠近 y 的那个 b点连向 x 有边(容易用抽屉原理证明)。于是就可以将 L 变成一个环 R，即先从 b 到 y，然后从 y 到a，然后从a 到 x，最后从 x 回到 b（见下图）yxab于是环。最终就得到了一个更长的环 R，只要当前环的长度小于 n，都能构造出更长的能构造出一个长度为 n 的环，这就是一个 hamilton 回路。这个构造的方法很巧妙。其实构造的过程只需要保

3、证任意两点的度数和大于等于 n 即可，题目给出的条件要比这个条件充分多了，因此条件可以给成任意两点的度数和大于等于 n。参考程序constINFILE = ;OUTFILE = ;varn : long;g : array 1.1001 , 1.1001 of list : array 1.10000 of long;h : array 1.1001 of head , tail : long;f : array 1.1001 of longa : array 1.1001 of long;procedure swap(var a , b : long); varc : long;beginc

4、 := a;a := b;b := c;end;procedure init; vari , j , k : long;beginReadln(n);fillchar(g , sizeof(g) , false); for i := 1 to n dobeginwhile (not eoln) do beginRead(k);if (k = i) then continue; gik := true;gki := true;end;Readln;end;end;procedure add(k : long); vari : long;beginhk := true;for i := 1 to

5、n doif (gki) and (fi = 0) then fi := k;end;procedure Reverse(i , j : long); beginwhile (i j) do beginswap(listi , listj); inc(i);dec(j);end;end;procedure Move(k : long); vari , j : long;beginfor i := head to tail doif (listi = k) then beginj := i; break;end; Reverse(head , j - 1); Reverse(j , tail);

6、 Reverse(head , tail);end;procedure main; vari , j , k : long;beginhead := 5000; tail := 5000; list5000 := 1;fillchar(h , sizeof(h) , false);fillchar(f , sizeof(f) , 0); add(1);while (tail - head + 1 n) do beginfor i := 1 to n doif (not hi) and (fi 0) then begink := i; break;end; Move(fi); while (tr

7、ue) do begink := -1;for i := 1 to n doif (not hi) and (glistheadi) then begindec(head); listhead := i; k := i;add(k); break;end;if (k = -1) then break;end;while (true) do begink := -1;for i := 1 to n doif (not hi) and (glisttaili) then begininc(tail); listtail := i; k := i; add(k); break;end;if (k =

8、 -1) then break;end;if (glistheadlisttail) then continue;for i := head + 1 to tail - 1 doif (glistheadlisti) and (glisti - 1listtail) then beginMove(listi);Reverse(head + tail - i + 1 , tail); break;end;end;Move(1);for i := head to tail do Wri Wrin(1);isti , );end;beginassign(input , INFILE); reset(

9、input);assign(output , OUTFILE);rewrite(output);init;main;close(input);close(output);end.原题122. The bookTime Limit: 0.4 sec, Memory Limit: 1.5 MBThere is a group of N (2=N=1000) people which are numbered 1 through N, and everyone of themhas not lessn (N+1) / 2 friends. A man with number 1 has the bo

10、ok, which others want toread. Write the program which finds a way of transferring the book sot it will visit everyman only once, passing from the friend to the friend, and,Note: if A is a friend of B then B is a friend of A.ast, has come back to the owner.Inputline of inpontains number N. Next N lines contain information about friendships. (i+1)-thline of inpontains a list of friends of i-th man.OutputIf there is no solution then your program must output No solution.Else your program mustoutput exactly N+1 number: this sequenhould begin and should come to e