- HDU1693 Eat the Trees
这题应该是插头DP最入门的一题了吧……给定一个n*m棋盘(n,m<=11)，其中一些格子是被抠掉的，要求用一些哈米尔顿回路覆盖所有未被抠掉的格子。求有多少种方案。
因为这题没有限制回路的数量，所以连左插头右插头都不用记录了，也不用神马括号序列，直接记录某个位置有木有插头就可以了。转移完全木有限制，只要有个插头，随便往哪个方向跑都行（障碍物除外），随便怎么合并两个插头都可以…… 用二进制记录轮廓线的状态（有插头或木有插头）
代码在>这里< hdu的pascal编译器很蛋疼，不给用exit(xxx),<<,>>,qword等一堆东西，所以代码写的巨丑……
- URAL1519 Formula 1
陈丹琦论文的例题……题意和Eat the Trees基本相同，只是限制了必须用一个哈米尔顿回路来覆盖这个棋盘。
这样我们发现如果随便合并的话很可能合并出多个回路……因此我们需要记录一个插头是左插头还是右插头……两个连通的插头，在轮廓线上左边那个叫左插头，右边那个叫右插头。这样我们就可以知道把两个插头合并会不会产生一个回路。把一个左插头和一个右插头合并会产生回路，否则不会。于是合并时要先看一下两个插头是左插头还是右插头。这样轮廓线就要用三进制记录了（木有插头、左插头、右插头）
代码在>这里<
- PKU1739 Tony’s Tour
这题和上一题基本类似……只是起点终点是给定的，一个在左下角一个在右下角，也就是说，要用一条起点终点给定的哈米尔顿路来覆盖这个棋盘。
有一个比较讨巧的解决方法就是人为虚拟地把起点终点连起来，这样就转化成了上一题。当然也可以用独立插头来做，具体看下一题。
代码在>这里<
4.PKU3133 Manhattan Wiring
这题题意比较怪……就是给定一个棋盘，有一些格子是不能经过的，然后棋盘上有两个[2]和两个[3]。要求用两条线把这两个[2]连起来，再把两个[3]连起来。然后两条线不能共用格子。要求求出这两条线的最短长度和。
这题很容易误导人往网络流方向想……但实际上网络流似乎是不行的。正解是插头DP。
用三进制表示轮廓线：0表示木有插头。1表示有一个从某个[2]来的插头。2表示有某个从[3]来的插头……
然后…… 为了记录方便，用类似01的格式表示当前关键格的状态，第一个数是左插头状态，第二个是上插头状态。同样的， 用类似01的格式表示当前关键格转移出来的状态，第一个数是下插头状态，第二个是右插头状态。X表示1或2
对于普通的格子：
00 -> 00/11/22
0X/X0-> 0X/X0
11/22 -> 00
12/21 -> 挂了
对于障碍格：
00 -> 00
其他的 -> 全挂了
对于标记有[2]、[3]的格子：
0X/X0 -> 00 其中X必须是格子上的数。
00 -> 0X/X0 其中X必须是格子上的数。
其他的全挂了
最后那种情况就是独立插头。可以发现其他情况里，关键格都有两个插头，但独立插头所在关键格里只有一个插头。这样就把哈米尔顿回路转化成了哈米尔顿路径。
有人可能会说，你这道题用的方法可能会产生多条回路的啊，那不就悲剧了吗。其实不然。这种方法确实会产生多条回路，但题目求的是最小值，那些产生多余回路且满足要求的方法很明显比不产生多余回路的方法要来的差，不会影响到最终答案。
代码在>这里<