收藏
关注
N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。
Input第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)
Output输出最小生成树的所有边的权值之和。
Input示例9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8
Output示例37
用prim算法可以完成.
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 #define N 1005
6 #define inf 0x3f3f3f3f
7 #define mem(a) memset(a,0,sizeof(a))
8 using namespace std;
9 int cost[N][N];//表示两点之间的距离,不存在则设为inf
10 int mincost[N];//从x集合出发到每个顶点的最小值
11 bool used[N];//判断是否在集合中的布尔数组
12 int n,m;
13
14 int prim(){
15 for(int i=0;i<n;i++){//初始化mincost数组和used布尔数组
16 mincost[i]=inf;
17 used[i]=false;
18 }
19 mincost[0]=0;//赋给其初值
20 long long int ans=0;
21
22 while(true){
23 int v=-1;
24 //从不属于x的顶点中选取从x到其权值最小的顶点
25 for(int u=0;u<n;u++)
26 if(!used[u]&&(v==-1||mincost[u]<mincost[v]))
27 v=u;
28
29 if(v==-1)
30 break;//条件成立则说明所有的点都已经加入
31 used[v]=true;//把顶点加入
32 ans+=mincost[v];//把边的长度加到结果里
33
34 for(int u=0;u<n;u++){
35 if(!used[u])
36 mincost[u]=min(mincost[u],cost[v][u]);
37 }
38 }
39 return ans;
40 }
41 int main(){
42 cin>>n>>m;
43 int x,y,z;
44 memset(cost,inf,sizeof(cost));
45 while(m--){
46 scanf("%d%d%d",&x,&y,&z);
47 cost[--x][--y]=z;
48 cost[y][x]=z;
49 }
50 long long int k=prim();
51 cout<<k<<endl;
52 return 0;
53 }
kruskal算法解题:
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 #define N 50005
6 using namespace std;
7 struct Node{//定义结构体,分别加入两个点和两个点之间的权值
8 int u,v,cost;
9 };
10 bool cmp(Node a,Node b){//自定义排序
11 return a.cost<b.cost;
12 }
13 Node node[N];
14 int fa[N];
15 int n,m;
16 int Find(int x){//并查集查找
17 return x==fa[x]?x:Find(fa[x]);
18 }
19 void init(){//初始化fa数组
20 for(int i=0;i<n;i++){
21 fa[i]=i;
22 }
23 return ;
24 }
25 int kruskal(){
26 init();
27 long long int cnt=0;
28 int t=0;
29 for(int i=0;i<m;i++){
30 Node e=node[i];
31 int x=Find(e.u);
32 int y=Find(e.v);
33 if(x!=y){//如果父节点相同,则构成了一个环,那么就不能将其放入里面,跳过
34 fa[x]=y;
35 cnt+=e.cost;
36 t++;
37 }
38 if(t==n-1) break;//如果所加的边达到了n-1条,跳出循环
39 }
40 return cnt;
41 }
42 int main(){
43 scanf("%d%d",&n,&m);
44 for(int i=0;i<m;i++){
45 scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].cost);
46 }
47 sort(node ,node+m,cmp);
48 long long int ans=kruskal();
49 printf("%lld\n",ans);
50 return 0;
51 }