UVA 10054 The Necklace

题意

给出若干二色珠子,问你能不能把他们重新排列以连成一条环,使得相邻的两个珠子颜色相同。

思路

转化为欧拉图问题。令结点代表不同的颜色,连接两个结点的边代表珠子。把珠子连成项链的过程转化为求出一种走法使得我们可以走完全部的边然后返回起点。这就是典型的欧拉回路问题了。

如果不会这个知识,请参考:有关欧拉图问题的一些总结

代码

 

UVa 11488 Hyper Prefix Sets

Trie树,静态方式的话(用数组保存节点),可以比较简单的实现遍历,动态方式(new+指针)还要写搜索。。。

Asia – Tokyo – 2007/2008 UVa 3887 Slim Span

在kruskal的基础上,每一次干掉一条边,再kruskal一次,如果得到了生成树,就看看他的最大边权-最小边权是不是可以更新当前最优解,然后反复这么搞把所有边都搞掉就完成遍历了,因为事先已经对边权排序了,这么做并不会丢解。

UVA 10420 List of Conquests

STL的使用小练习

Scroll to top