TopCoder SRM496 Div1 YetAnotherHamiltonianPath解题报告

题意:

有N<=50个城市,每个城市有一个名字(一个字符串)。从城市s走到城市t的代价是:|s|^2+|t|^2-LCP(s,t)^2.其中LCP(s,t)指s和t的最长公共前缀长度。求一条开始于0号城市,结束于1号城市的最短哈密尔顿路径。


分析:

出于方便起见,我们将问题转化成“求一条最短的哈密尔顿回路,使得回路中0,1号城市相邻”。
先不考虑这个相邻,单看“求一条最短的哈密尔顿回路”:

首先我们按照城市名字的首字母将其分类,并将同一类的放在一起。

例如:城市名可能是“asdf,aqwe,bpdr,btr”,那么”asdf”和”aqwe”就是同一类,”bpdr”和”btr”是同一类。

显然,在最短的哈密尔顿回路中,同一类一定是放在一起的。而对于同一类,我们又可以按照第二个字母将其分类……如此递归下去。

例如:有五个城市,名称是”aab”,“ccf”,”ab”,“aac”,”cd”。

第一层划分:{ “aab” , “ab” , “aac” } , { “ccf” , “cd” }

第二层划分:{ { “aab” , “aac” } , { “ab” } } , { { “ccf” } , { “cd” } }

第三层划分:{ { { “aab” } , { “aac” } } , { “ab” } } , { { “ccf” } , { “cd” } }

这样的结果:”aab” -> “aac” -> “ab” -> “ccf” -> “cd” -> “aab”就一定是一个最短的哈密尔顿回路。

在讨论如何让0和1相邻之前,先看一下如何实现这个“划分”的细节;

step 1:设i,j两个指针,让i从”aab”开始扫描。

step 2:让j指向i的下一个位置,顺序遍历后面的城市名称,如果首字母和 i 指向的城市相同,就将它和 j 指向的城市交换,并把 j 指针加1.

step 3:如此扫描一遍后,数组变成了{“aab”,”ab”,”aac”,”ccf”,”cd”},j指向”ccf”。

step 4:将i赋值为j,回到step 2进行下一次循环。

如何让0和1相邻呢?设0号城市的名字是S0,1号城市的名字是S1.

遵循三个原则:①如果当前这一类中既有S0又有S1,就设法让S0和S1相邻。②如果当前这一类中只有S0没有S1,就设法把S0排在最后。③如果当前这一类中只有S1没有S0,就设法把S1排在最前。

根据上面所述的划分细节不难看出,在①中S0和S1所在的子集一定相邻。②和③保证:S0在当前子集的最后,S1在当前子集的最前。

例如:在上例中S0=”aab”,S1=”cd”。

1:划分{“aab”,“ccf”,”ab”,“aac”,”cd”}:根据①我们将集合改成{“aab”,”cd”,”ccf”,”ab”,”aac”},划分成:{{“aab”,”ab”,”aac”},{“cd”,”ccf”}},”aab”和”cd”所在的子集相邻。

2:从1处递归划分{“aab”,”ab”,”aac”}:根据②我们将集合改成{“ab”,”aac”,”aab”},划分成:{{“ab”},{“aac,aab”}}。

3:从2处递归划分{“aac”,”aab”}:根据②,集合还是{“aac”,”aab”},划分成:{{“aac”},{“aab”}}。

4:从1处递归划分{“cd”,”ccf”}:根据③,集合还是{“cd”,”ccf”},划分成:{{“cd”},{“ccf”}}。

5:所有划分完成,数组变为:{“ab”,”aac”,”aab”,”cd”,”ccf”}。其中S0和S1相邻,并且是一个最短的哈密尔顿回路。

最后求一遍哈密尔顿回路的总长,减去S0->S1的花费即可。这道题数据范围很小,基本不用考虑时间复杂度。


代码:


发表评论

电子邮件地址不会被公开。 必填项已用*标注