wmdcstdio的博客

题意：

给一个0~N-1的图，点i向点(2*i)%N和点(2*i+1)%N连有向边。求从0到0的哈密尔顿回路。

（怎么又是一道哈密尔顿回路）

做法：

题意：

有N “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号[……]

继续阅读