题目链接：
https://vjudge.net/problem/ZOJ-1586
题目大意：
首先给一个t，代表t个测试样例，再给一个n，表示有n个QS装置，接下来一行是n个QS装置的成本。接下来是n*n的矩阵，表示每两个QS 装置之间链接需要的费用。求在全联通的情况下求最少费用。
思路：
这里需要求最少费用，由于点和边都有权值，索性直接把两端点的权值加到边的权值上，那就变成了一个裸的MST题目了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<stack> 8 #include<map> 9 #include<sstream>10 using namespace std;11 typedef long long ll;12 const int maxn = 2e3 + 10;13 const int INF = 1 << 30;14 int dir[4][2] = {1,0,0,1,-1,0,0,-1};15 int T, n, m, x;16 int Map[maxn][maxn];//存图17 int lowcost[maxn], mst[maxn];18 int a[maxn];19 void prim(int u)//最小生成树起点20 {21 ????int sum_mst = 0;//最小生成树权值22 ????for(int i = 1; i <= n; i++)//初始化两个数组23 ????{24 ????????lowcost[i] = Map[u][i];25 ????????mst[i] = u;26 ????}27 ????mst[u] = -1;//设置成-1表示已经加入mst28 ????for(int i = 1; i <= n; i++)29 ????{30 ????????int minn = INF;31 ????????int v = -1;32 ????????//在lowcost数组中寻找未加入mst的最小值33 ????????for(int j = 1; j <= n; j++)34 ????????{35 ????????????if(mst[j] != -1 && lowcost[j] < minn)36 ????????????{37 ????????????????v = j;38 ????????????????minn = lowcost[j];39 ????????????}40 ????????}41 ????????if(v != -1)//v=-1表示未找到最小的边,42 ????????{//v表示当前距离mst最短的点43 ????????????//printf("%d %d %d\n", mst[v], v, lowcost[v]);//输出路径44 ????????????mst[v] = -1;45 ????????????sum_mst += lowcost[v];46 ????????????for(int j = 1; j <= n; j++)//更新最短边47 ????????????{48 ????????????????if(mst[j] != -1 && lowcost[j] > Map[v][j])49 ????????????????{50 ????????????????????lowcost[j] = Map[v][j];51 ????????????????????mst[j] = v;52 ????????????????}53 ????????????}54 ????????}55 ????}56 ????//printf("weight of mst is %d\n", sum_mst);57 ????cout<<sum_mst<<endl;58 }59 int main()60 {61 ????cin >> T;62 ????while(T--)63 ????{64 ????????cin >> n;65 ????????for(int i = 1; i <= n; i++)cin >> a[i];66 ????????for(int i = 1; i <= n; i++)67 ????????{68 ????????????for(int ?j= 1; j <= n; j++)69 ????????????{70 ????????????????cin >> Map[i][j];71 ????????????????if(i == j)continue;72 ????????????????Map[i][j] += a[i] + a[j];//把两个端点的权值加在边上，就转变成裸的MST题目了73 ????????????}74 ????????}75 ????????prim(1);76 ????}77 ????return 0;78 }ZOJ-1586 QS Network---最小生成树Prim
原文地址：https://www.cnblogs.com/fzl194/p/8724624.html