聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

POJ 1021 2D-Nim

2013-09-05 22:10 浏览: 1125230 次 我要评论(0 条) 字号:

总结

就是连通性和图的同构判断。

分析

找出属于同一组的点很简单,DFS就可以搞定。图的同构可以用图的Hash来判断。这个不是我想出来的,是网上看来的:
$sumnolimits_{i,]} distance(p_i, p_j)$
即同一组中所有点的距离加起来,这个数值做为这个图的哈希值。我不知道如何去证明,但是目前我没找到反例。至少这个题可以用。如果有同学可以帮证明可以或是不可以,那就多谢了。

happyac 2013-09-05 11:36 发表评论


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复