题目大意：
给出的案例结果得出步骤，如下图所示，从结点1开始查找，找出的一条路径如绿色部分所标注。（关键处在于连接每条路径所需要的适配器的价格得加上去）
代码实现：
1 #include<iostream> 2 #include<cstdio> 3 using ?namespace std; 4 #define MAX 1000 5 //注意此处范围得按照题意设置为>=1000，否则会Segmentation Fault 6 #define MAXCOST 0x7fffffff 7 ?8 int graph[MAX][MAX]; 9 10 int prim(int graph[][MAX], int n)11 {12 ????int lowcost[MAX];13 ????int mst[MAX];14 ????int i, j, min, minid, sum = 0;15 ????for (i = 2; i <= n; i++)16 ????{17 ????????lowcost[i] = graph[1][i];18 ????????mst[i] = 1;19 ????}20 ????mst[1] = 0;21 ????for (i = 2; i <= n; i++)22 ????{23 ????????min = MAXCOST;24 ????????minid = 0;25 ????????for (j = 2; j <= n; j++)26 ????????{27 ????????????if (lowcost[j] < min && lowcost[j] != 0)28 ????????????{29 ????????????????min = lowcost[j];30 ????????????????minid = j;31 ????????????}32 ????????}33 ????????sum += min;34 ????????lowcost[minid] = 0;35 ????????for (j = 2; j <= n; j++)36 ????????{37 ????????????if (graph[minid][j] < lowcost[j])38 ????????????{39 ????????????????lowcost[j] = graph[minid][j];40 ????????????????mst[j] = minid;41 ????????????}42 ????????}43 ????}44 ????return sum;45 }46 47 int main()48 {49 ????int i, j, k, t, en, n,x, y, cost,pre[1001];50 ????scanf("%d",&t);51 ????while(t--){52 ????????scanf("%d",&n);53 ????????for(i=1;i<=n;i++)54 ????????????scanf("%d",&pre[i]);55 ????????for (i = 1; i <= n; i++)56 ????????{57 ????????????for (j = 1; j <= n; j++)58 ????????????{59 ????????????????graph[i][j] = MAXCOST;60 ????????????}61 ????????}62 ????????//构建图G63 ????????for(i = 1; i <= n; i++){64 ????????????for(k=1;k<=n;k++){65 ????????????????scanf("%d",&graph[i][k]);66 ????????????????graph[i][k]+=pre[i];//直接将每条路径上存在的适配器价格给加到权值里面去即可67 ????????????????graph[i][k]+=pre[k];68 ????????????}69 ????????}70 ????????cost = prim(graph, n);71 ????????cout <<cost << endl;72 ????}73 ????return 0;74 }最小生成树-QS Network（Prim）
原文地址：https://www.cnblogs.com/LJHAHA/p/10356697.html