icontofig | 发布于 2020-02-06 20:52:24 | 阅读量 312 | 最小生成树 Trie
发布于 2020-02-06 20:52:24 | 最小生成树 Trie
51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心
题解每条边的权值都是根据每个点的定值通过二进制异或得出的。 如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。 假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。 这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。 于是所有的答案统计全部都在01trie上。 接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。 所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。 假如一个叶节点上有k个点(k > 2),
继续阅读
icontofig | 发布于 2019-03-24 23:21:38 | 阅读量 247 | 最小生成树
发布于 2019-03-24 23:21:38 | 最小生成树
UVALive-6437 题外话还是vjudge不错233,可以不用注册新帐号了。 这是本人第一篇关于Uva题目的题解。 题目链接放上面大家自己去点,因为PDF格式真的是粘不过来。 题目大意现在有n个城市,城市之间有m个预期修筑电缆的方案线,其中有k个城市有发电站。 现在要求建设电线,使得每个城市都能有供电。由于每条线路有一定的花费,所以现在要求满足题目的最小花费。 题解其实题目里已经简化成一个图了,剩下的就是自己想该怎么解决了。 其实思考一下,这好像跟用最小代价选边使得图连通的问题非常接近,第一感觉就是个最小生成树啊,直接kruskal或者Prim就行了啊。 但是回过头来想想,好像有那么一点
继续阅读