Krruskal最小生成树-安慰奶牛题解

我是题面

屏幕截图 2025-05-17 183605
屏幕截图 2025-05-17 183616
image

fammer john 限时回归
下面是题解:
根据题意,场是点,道路是边,他要删掉边,不就是最小生成树?
Kruskal秒了(bushi)
直接搬模板你只会得到一个大大的WAAAAAAA
prim肯定是不可以的,会爆
john还需要安慰奶牛
你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej,而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接(找最小生成树)。

每次你到达第i个牧场的时候(即使你已经到过),你必须花去Ci的时间和奶牛交谈走之前找好的最小生成树的路,每个点可能会经过多次,每经过一次就谈一次话ci,可以自己脑补一下,就像dfs回溯遍历每一条路,直到走完。
说明这道题需要同时处理点权和边权, :expressionless_face:
那该怎么办?
:nerd_face: :backhand_index_pointing_down:
首先,这条路要被来回走两遍(因为是树),所以在总权值里要有它× 2 \times2×2

其次,每头奶牛会被安慰两次,这样可以想到要加入2倍的点权,但是再更新下一条时就又会被重复计算,所以只需要算一次就行。

这样中间节点都是两次,两端是1次,但是题目的特殊要求要起点算2次,所以先在读入点权时就找到最小的数最后加入即可

我是部分代码
for(int i=1; i<=m; i++) {
	int xx=find();
	int yy=find();
	if(xx!=yy) {
		fa[xx]=yy;
		sum+=a[i].v;
		[a[i].x]++;
		[a[i].y]++;
	}
}

我的代码里做了个处理
过不了可以尝试加一下

	for(int i=1;i<=; i++) {
		cin>>a[i].x>>a[i].y>>a[i].v;
		a[i].v=2*a[i].v+c[a[i].x]+c[a[i].y];
	}

并查集find查找一下属不属于同一个集合内,递归下去寻找并查集不会来学最小生成树的是这个 :+1:
最后打一个小擂台

	int minn=0x3f3f3f3f;
	for(int i=1; i<=n; i++){
		if(minn>c[i]){
			minn=c[i];
		}
	}
	sum+=minn;

秒了

蒟蒻第一次写题解,有问题欢迎大蛇指出 :rolling_on_the_floor_laughing:

fammer John 是个人物 :face_with_tears_of_joy:

1 个赞

%%%但是,您说得对

1 个赞

+1

1 个赞