[问题] ZeroJudge-d688(已解决)

楼主: fatcat8127 (胖胖猫)   2019-03-27 18:21:27
关于这题的作法一开始是想从旅行推销员的方式将所有相互连通的点,以状态压缩方式更新
状态。
感谢cutecpu大大的协助。
解法的核心是利用动态规划的状态转移,枚举所有的状态,针对现在的状态找到一条存在的
边,边的一点在集合中另一点不在时就可以状态转移。
cutecpu大大的做法巧妙在在判断上述条件是否存在时是O(n)而不是枚举任两个点的边。
保留错误的Code(https://www.codepile.net/pile/P2JW1nq5)
以下是用土炮方式捞出来的第二笔测资:
第二笔测资的答案是84
7 10
2 5
4 7
2 4
6 2
7 3
7 1
6 5
7 5
1 2
5 3
作者: cutekid (可爱小孩子)   2019-03-27 20:05:00
http://codepad.org/gNZ7n7aK ←修改过后 AC 的 C 程式码

Links booklink

Contact Us: admin [ a t ] ucptt.com