[原]HDU-1598-find the most comfortable road(暴力枚举+Kruskal最小生成树)

题意:

给出一个图,然后Q个询问,每次询问从一个节点到另一个节点,联通图中的“最大边和最小边之差”的最小值,但如果节点之间不连通,则输出-1.

思路:由于询问Q < 11,m < 1000,所以O(Q*n^2),Q*n^2 < 10^8,用最小生成树的思路,在给图上的边排好序的基础上,每次枚举最小边,然后做并查集枚举最大边,当查询的路径相通的时候,如果差值比上一次枚举最小边的差值小的时候,更新。

AC代码:

{CSDN:CODE:330547}
作者:u011652573 发表于2014-5-6 20:20:56 原文链接
阅读:47 评论:0 查看评论
上一篇:WCF扩展之实现ZeroMQ绑定和protocolBuffer消息编码(一)概要设计


下一篇:emacs命令记录