两道Prim解法范例题型，简单的裸Prim，且两题相较以边为重心的Kruskal解法而言更适合以点为重心扩展的Prim解法。
ZOJ1586-QS Network
题意：见Code
题解：直接的MST题型，本题的图为稠密图，因此适合以点为扩展导向的Prim算法（代码量也较少）。
大抵是先以某点A为中心，标记点A，访问其邻接点，更新全图到该点的距离(不通路以INF表示)，找出最短距离的点B
标记最短距离的B点，然后访问其邻接点，更新邻接点到B点的最短距离，找出最短距离的点C...以此类推...
将已标记的点作为生成树M节点，此时M就是所求最小生成树。
该算法的实际核心可以理解为每次更新所有未加入生成树M的点到集合M（将M理解为一个整体）的最短距离。
因此该算法普遍将该最短距离简化为一个数组，教材上一般命名为lowcost[MAX]，不断更新此数组的最小值即可。
//Prim-裸
//建立QS网络，一条网线需要一定成本及两点处的适配器成本，求最小费用
//本题的边数可到10^6,而点只到10^3，因此理论上说用prim比Kruskal明智(也比较好写)
//Time:30Ms Memory:4228K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; #define INF 0x3f3f3f3f
#define MAX 1005 int n;
int d[MAX][MAX];
int adapter[MAX]; //适配器价格
int lowcost[MAX]; //各点到已生成集合的最小路长
bool v[MAX]; //已访问的点 void prim()
{
memset(lowcost, INF, sizeof(lowcost));
memset(v, false, sizeof(v)); int minv = ;
v[] = true;
for (int i = ; i < n; i++)
lowcost[i] = d[i][];
for (int i = ; i < n; i++)
{
int mind = INF;
int k; //最近的结点编号
for (int j = ; j < n; j++)
{
if (!v[j] && mind > lowcost[j])
{
mind = lowcost[j];
k = j;
}
} minv += mind;
v[k] = true;
for (int j = ; j < n; j++)
if(!v[j]) lowcost[j] = min(lowcost[j], d[k][j]);
}
printf("%d\n", minv);
} int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &adapter[i]);
for (int i = ; i < n; i++)
for (int j = ; j < n; j++)
{
scanf("%d", &d[i][j]);
d[i][j] += adapter[i] + adapter[j];
}
prim();
}
return ;
}
POJ1789(ZOJ2158)-Truck History
题意：由7位编码组成的卡车编码，两个编码间的距离以对应位置的编码不同个数为总距离，例如aaaaaaa,abaabaa两个编码距离为2，求使得所有卡车编码最近的距离。（与实际题意有一点不同，为了方便理解稍微改编了一些）
题解：理解了题意就好做了，本质依然是求一个裸的MST。
Prim算法思路参照上题题解。
//Prim-裸
//POJ1789-ZOJ2158
//边数4*10^6,点2000，稠密图较适合Prim
//Time:657Ms Memory:15872K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; #define INF 0x3f3f3f3f
#define MAX 2001 int n;
int d[MAX][MAX];
int lowcost[MAX];
bool v[MAX];
char s[MAX][]; void prim()
{
memset(lowcost, INF, sizeof(lowcost));
memset(v, false, sizeof(v));
int minv = ;
v[] = true;
for (int i = ; i < n; i++)
lowcost[i] = d[i][];
for (int i = ; i < n; i++)
{
int mind = INF;
int k;
for (int j = ; j < n; j++)
{
if (!v[j] && mind > lowcost[j])
{
mind = lowcost[j];
k = j;
}
}
minv += mind;
v[k] = true;
for (int j = ; j < n; j++)
if (!v[j]) lowcost[j] = min(lowcost[j], d[k][j]);
}
printf("The highest possible quality is 1/%d.\n", minv);
} int main()
{
while (scanf("%d", &n), n)
{
for (int i = ; i < n; i++)
scanf("%s", s[i]);
memset(d, , sizeof(d));
for (int i = ; i < n; i++)
for (int j = i+; j < n; j++)
for (int k = ; k < ; k++)
d[j][i] = d[i][j] += s[i][k] != s[j][k];
prim();
}
return ;
}