Tag-最小生成树

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-02-06 20:52:24 |  0 Comments  |  最小生成树 Trie

51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心

题解

每条边的权值都是根据每个点的定值通过二进制异或得出的。

如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。

假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。

这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。

于是所有的答案统计全部都在01trie上。

接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。

所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。

假如一个叶节点上有k个点(k > 2),那么对应的建边方案就是kk-2种。

当从叶节点向上走的时候,假设某节点的父亲节点的两个子树上都有点存在(即两个子树都非空),那么我们肯定要用边把这两个子树连起来,连起来的时候就需要顺着trie往下找异或值最小的边的权值是多少。

细节不是很好解释,不过这种思路是二进制异或时一种常见的贪心思路,可以看代码理解一下。

这个题不需要并查集,因为当刚向上走到某个点时,如果其两个子树都非空,那么这两个子树代表的两个已经构建好的生成树必然属于两个不同的连通块。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
    int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
    ll ans = 1;
    while (y){
        if (y & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}
void insert(int &d, int dep, int v){
    if (!d)
        d = ++sz;
 2019-03-24 23:21:38 |  0 Comments  |  最小生成树

UvaLive-6437 Power Plant(变种Kruskal)

UVALive-6437

题外话

还是vjudge不错233,可以不用注册新帐号了。

这是本人第一篇关于Uva题目的题解。

题目链接放上面大家自己去点,因为PDF格式真的是粘不过来。

题目大意

现在有n个城市,城市之间有m个预期修筑电缆的方案线,其中有k个城市有发电站。

现在要求建设电线,使得每个城市都能有供电。由于每条线路有一定的花费,所以现在要求满足题目的最小花费。

题解

其实题目里已经简化成一个图了,剩下的就是自己想该怎么解决了。

其实思考一下,这好像跟用最小代价选边使得图连通的问题非常接近,第一感觉就是个最小生成树啊,直接kruskal或者Prim就行了啊。

但是回过头来想想,好像有那么一点不对劲的地方。

你看那个样例演示图,明明是不连通的啊。

这是因为本身就有发电站的城市不一定要跟外部连通。所以这题就不是一个纯粹的最小生成树了。但是还是很像,所以我们选择对kruskal进行一下修改。

记录一个cnt,表示当前供上电城市的数量,并查集跟普通kruskal一样的路径压缩写法,不过要加上一个siz数组来记录这一个并查集里有多少城市。

排序也和正常的kruskal一样。

关键点来了。

如何合并并查集啊?以及cnt怎么更新啊?

由于本身就有发电站的城市不一定要和外部连通,所以我们这样:

定义当前边的两个端点的父亲(并查集find后)为x,y,分以下三种情况:

1.x,y都不是有发电站的城市:直接合并并查集,f[y] = x;siz[x] += siz[y];ans(总花费) += dis。

2.x,y都是有发电站的城市:直接跳过,不需要这条边,也不计入答案。

3.x为有发电站的城市,y则是没有发电站的城市:将y所在的并查集合入x所在的并查集内,维持x在并查集的根节点的位置,并更新当前已经有供电的城市数cnt。

f[y] = x;siz[x] += siz[y];ans += dis;cnt += siz[y];

cnt的初值就是赋为k,表示一开始共有k个城市有供电。

这样这个问题就很轻松的解决了。

为什么不选择Prim?因为Prim没有像Kruskal这样顺手的并查集啊QAQ。(好吧实际上是我Kruskal打习惯了)

参考代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
	int num = 0;
	char c;
	bool flag = f
Title - Artist
0:00