此题是最基础的最小生成树的题目，有两种方法， 一个是prim一个是kruskal算法，前者利用邻接矩阵，后者是利用边集数组
prim算法的思想是：一个点一个点的找， 先找从第一个点到其他点最小的， 把权值存放到一个lowcost的数组中，然后继续找下一个点，然后更新lowcost数组，注意，这时的lowcost不完全是第二个点到所有点的距离，而是，其他点到最小生成树的距离，然后一步一步的求，知道求完所有点
kruskal算法的思想是：先把边集数组按照权值进行排序，之后从最小的往上找，这时有个前提，就是不能有环，这样就能保证最大连通量为1，借助father数组
代码如下：
方法一(Prim):
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX = + ;
const int INFINITY = ;
int map[MAX][MAX];
int Sum;
int v, e;//v来存点的个数，e来存边的个数
void mini_span_tree_prim()
{
int lowcost[MAX];
lowcost[] = ;//标记已经加到最小生成树中
for(int i = ; i <= v; i++)
{
lowcost[i] = map[][i];
}
for(int i = ; i <= v; i++)
{
int j = ;
int index = ;
int minweight = INFINITY;
while(j <= v)
{//找出最小的边来，并保存其坐标
if(lowcost[j] != && lowcost[j] < minweight)
{
minweight = lowcost[j];
index = j;
}
j++;
}
lowcost[index] = ;//标记已经加到最小生成树中
Sum += minweight;
for(j = ; j <= v; j++)
{//判断没有加到最小生成树中的和比当前权值要小的点
if(lowcost[j] != && lowcost[j] > map[index][j])
{
lowcost[j] = map[index][j];
}
}
}
}
int main()
{
//freopen("1.txt", "r", stdin);
int n;
scanf("%d", &n);
while(n--)
{
Sum = ;
scanf("%d %d", &v, &e);
int t1, t2, t3;
memset(map, , sizeof(map));
for(int i = ; i <= v; i++)
{
map[i][i] = ;
}
for(int i= ; i < e; i++)
{
scanf("%d %d %d", &t1, &t2, &t3);
map[t1][t2] = t3;
map[t2][t1] = t3;
}
int mincost = INFINITY;
for(int i = ; i < v; i++)
{
scanf("%d", &t1);
mincost = min(mincost, t1);
}
mini_span_tree_prim();
printf("%d\n", Sum + mincost);
}
return ;
}
方法二(Kruskal):
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct Node{
int s;
int e;
int weight;
}Node;
const int MAX = + ;
const int INFINITY = ;
Node arr[MAX * ];
int father[MAX];
int sum;
int v, edges; bool cmp(Node a, Node b)
{
return a.weight < b.weight;
} int find(int f)
{
while(father[f] > )
f = father[f];
return f;
}
//生成最小生成树
void mini_span_tree_kruskai()
{
int n, m;
int cnt = ;
for(int i= ; i < edges; i++)
{
n = find(arr[i].s);
m = find(arr[i].e);
if(cnt == v - )//优化，如果找到了n-1条边，这时退出就行了
break;
if(n != m)//判断是否构成了环
{
father[m] = n;
sum += arr[i].weight;
cnt++;
}
}
} int main()
{
int n;
scanf("%d", &n);
while(n--)
{
memset(arr, , sizeof(arr));
memset(father, , sizeof(father));
sum = ;
scanf("%d %d", &v, &edges);
for(int i = ; i < edges; ++i)
{
scanf("%d %d %d", &arr[i].s, &arr[i].e, &arr[i].weight);
}
int mincost = INFINITY;
int t;
for(int i = ; i <= v; i++)
{
scanf("%d", &t);
mincost = min(mincost, t);
}
sort(arr, arr + edges, cmp);//排序
// for(int i = 0; i < edges; i++)
// printf("%d %d %d\n", arr[i].s, arr[i].e, arr[i].weight);
// printf("%d\n", mincost);
mini_span_tree_kruskai();
printf("%d\n", sum + mincost); }
return ;
}