hiho#1097最小生成树一·Prim算法

题目链接:https://hihocoder.com/problemset/problem/1097

从单一顶点开始,Prim 算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。
输入:一个加权连通图,其中顶点集合为V,边集合为E;
初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {};
重复下列操作,直到Vnew = V:
在集合E中选取权值最小的边(u, v),其中u为集合Vnew中的元素,而v则是V中没有加入Vnew的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
将v加入集合Vnew中,将(u, v)加入集合Enew中;
输出:使用集合Vnew和Enew来描述所得到的最小生成树。

——Wikipedia

注:Prim和dijkstra算法好像啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstring>

const int MAX = 1000;
int A[MAX][MAX];
bool visit[MAX];
int main() {
int n,result=0;
memset(A,1,sizeof(A));
memset(visit,0,sizeof(visit));
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&A[i][j]);
//Prim
visit[1]= true;
for(int t=1;t<n;t++)
{
int k=0;
for(int i=1;i<=n;i++)
{
if(!visit[i] && A[1][i]<A[1][k])
k = i;
}

result += A[1][k];

visit[k]= true;

A[1][k]=A[k][1]=0;

for(int i=1;i<=n;i++)
{
if(!visit[i]&&A[1][i]>=(A[1][k]+A[k][i]))
{
A[1][i]=A[i][1] = A[1][k]+A[k][i];
}
}
}
printf("%d",result);

return 0;
}

Copyright © 2011 - 2018 活在梦里 All Rights Reserved.

myth 保留所有权利