【Acwing】最小生成树新的开始

àì夳堔傛蜴生んèń 2024-03-31 10:43 44阅读 0赞

[1146. 新的开始 - AcWing题库][1146. _ - AcWing]

题意：

![3a1a7b00e901471683c719cc62a6c82e.png][]

思路：

多起点的最小生成树

**对于多起点的图论问题，常用的处理方式是用一个虚拟源点，和所有起点连边，最好用n+1作为虚拟源点，用0有点容易搞混**

然后做一遍板子就好啦

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=3e2+10,mxe=(mxn*mxn)/2;
    struct ty{
    	int u,v,w;
    }edge[mxe<<1];
    bool cmp(ty x,ty y){
    	return x.w<y.w;
    }
    int n,m=0,x;
    int f[mxn],G[mxn][mxn];
    int find(int x){
    	return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
    	int f1=find(u),f2=find(v);
    	f[f1]=f2;
    }
    int kruskal(){
    	int res=0;
    	sort(edge+1,edge+1+m,cmp);
    	for(int i=1;i<=m;i++){
    		if(find(edge[i].u)==find(edge[i].v)) continue;
    		join(edge[i].u,edge[i].v);
    		res+=edge[i].w;
    	}
    	return res;
    }
    int main(){
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin>>n;
    	for(int i=1;i<=n+1;i++) f[i]=i;
    	for(int i=1;i<=n;i++){
    		cin>>x;
    		edge[++m].u=n+1,edge[m].v=i,edge[m].w=x;
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cin>>G[i][j];
    		}
    	}
    	for(int i=1;i<n;i++){
    		for(int j=i+1;j<=n;j++){
    			edge[++m].u=i;
    			edge[m].v=j;
    			edge[m].w=G[i][j];
    		}
    	}
    	cout<<kruskal()<<'\n';
    }

**总结：**

**虚拟源点的应用**

[1146. _ - AcWing]: https://www.acwing.com/problem/content/1148/
[3a1a7b00e901471683c719cc62a6c82e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/71e015e747374b6f9822cfde8cf02a52.png

发表评论取消回复

表情：

评论列表（有 0 条评论，44人围观）

还没有评论，来说两句吧...

相关阅读

相关【Acwing】最小生成树新的开始

[1146. 新的开始 - AcWing题库][1146. _ - AcWing] 题意： ![3a1a7b00e901471683c719cc62a6c82e.png][

àì夳堔傛蜴生んèń/ 2024年03月31日 10:43/ 0 赞/ 45 阅读

相关【Acwing】最小生成树联络员

[1143. 联络员 - AcWing题库][1143. _ - AcWing] 题意： ![fe41e24a599a40f7b7598a96b60fda66.png][]

左手的ㄟ右手/ 2024年03月31日 10:43/ 0 赞/ 59 阅读

相关【Acwing】最小生成树繁忙的都市

[1142. 繁忙的都市 - AcWing题库][1142. _ - AcWing] 题意： ![6713fc4c4e764ab4a0cf4d5daabd9296.png]

冷不防/ 2024年03月31日 10:42/ 0 赞/ 53 阅读

相关 Prim AcWing 858. Prim算法求最小生成树

Prim AcWing 858. Prim算法求最小生成树原题链接 [AcWing 858. Prim算法求最小生成树][AcWing 858. Prim]

逃离我推掉我的手/ 2023年09月28日 12:49/ 0 赞/ 138 阅读

相关最小生成树

最小生成树定义：在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即![(u, v)\\in E][u_ v_in E]），而

末蓝、/ 2022年09月20日 15:18/ 0 赞/ 197 阅读

相关生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）

生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）视频：[https://www.bilibili.com/video/BV1G64y187ke

Bertha 。/ 2022年09月12日 05:52/ 0 赞/ 200 阅读

相关最小生成树

邻接矩阵建图+prim朴素[算法][Link 1] 代码通过HDU1102 \[cpp\] [view plain][] [copy][view plain] 1.

超、凢脫俗/ 2022年06月09日 04:27/ 0 赞/ 65 阅读

相关最小生成树

有n个城市，m条道路，现在输入n到m的道路的长度，用最少的边将图连接，输出让图连接的最小值这道题我研究了好长时间才把答案看明白，现在给大家分享一下具体代码如下

爱被打了一巴掌/ 2022年05月30日 08:56/ 0 赞/ 174 阅读

相关最小生成树

问题提出：要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。问题分析：答案只能从生成树中找，因为要做到任何

雨点打透心脏的1/2处/ 2022年03月18日 12:28/ 0 赞/ 286 阅读

相关最小生成树

Jungle Roads [http://poj.org/problem?id=1251][http_poj.org_problem_id_1251] Descrip

逃离我推掉我的手/ 2021年11月29日 22:28/ 0 赞/ 415 阅读