普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法
算法过程图解：遍历点，用贪心法选择与集合内的点相连的点的最小值；
模板：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
using namespace std;
#define N 1005
typedef long long LL ;
int G[N][N];
int minn[N];///寻找最小权；
bool point[N]; int main(){
//freopen("in.txt","r",stdin);
memset(point, , sizeof(point));
int n, m, x, y, ans=;
scanf("%d%d", &n, &m);
for(int i=;i<=n;i++){
for(int j = ; j <= n; j++){
G[i][j] = INF;
}
}
for(int i = ; i <= m; i++) {
scanf("%d%d", &x, &y);
scanf("%d", &G[x][y]);
G[y][x] = G[x][y];
}
point[] = true;
for(int i = ;i <= n; i++) minn[i] = G[][i];
for(int i = ; i <= n; i++){
int k = , mi = INF;
for(int j = ; j <= n; j++){
if(!point[j] && minn[j] < mi){
mi = minn[j];
k = j;
}
}
ans += minn[k];
point[k] = true;
for(int s = ;s <= n; s++){
if(!point[s] && G[k][s] < minn[s])///保存了之前没有加入集合的边的权；
minn[s] = G[k][s];
}
}
printf("%d\n", ans);
return ;
}
题意：点是7位小写字母，边是小写字母间的不同字母数量（1-7）。求最小生成树。
边权：the number of positions with different letters in truck type codes.
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 2005 const double PI = acos(-1.0);
typedef long long LL ;
int n, dis[N][N], minn[N];
char x[];
string type[N];
bool point[N]; int Distance(int i, int j){
int len = , sum = ;
for(int k = ; k < len; k++)
if(type[i][k] != type[j][k])
sum++;
return sum;
}
int prim(){
point[] = true;
int ans = ;
for(int i = ; i <= n; i++) minn[i] = dis[][i];
for(int i = ; i <= n; i++){
int k = ; int mi =INF;
for(int j = ; j <= n; j++){
if(!point[j] && minn[j] <mi){
mi = minn[j];
k = j;
}
}
ans += minn[k];
point[k] = true;
for(int s = ; s <= n; s++){
if(!point[s] && dis[k][s] <minn[s])
minn[s] = dis[k][s];
}
}
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
while(~scanf("%d", &n) && n){
zero(dis);zero(point);MAX(dis);
for(int i = ; i <= n; i++){
scanf("%s", x);
type[i] = x;
}
for(int i = ; i<= n; i++){
for(int j = ; j < i; j++){
dis[i][j] = dis[j][i] = Distance(i, j);
}
}
printf("The highest possible quality is 1/%d.\n", prim());
}
return ;
}
题意：求最小生成树的最大边权；(英语实在太烂)
point：minimize the length of the longest highway
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 505 const double PI = acos(-1.0);
typedef long long LL ;
int T, n, dis[N][N], minn[N];
bool point[N]; int prim(){
point[] = true;
int ans = ;
for(int i = ; i <= n; i++) minn[i] = dis[][i];
for(int i = ; i <= n; i++){
int k = ; int mi =INF;
for(int j = ; j <= n; j++){
if(!point[j] && minn[j] <mi){
mi = minn[j];
k = j;
}
}
if(ans < minn[k]) ans = minn[k];
point[k] = true;
for(int s = ; s <= n; s++){
if(!point[s] && dis[k][s] <minn[s])
minn[s] = dis[k][s];
}
}
return ans;
} int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
scanf("%d", &T);
while(T--){
zero(point);zero(dis);zero(minn);
scanf("%d", &n);
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
scanf("%d", &dis[i][j]);
}
}
printf("%d\n", prim());
}
return ;
}
简单模板题，同上；
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 505 const double PI = acos(-1.0);
typedef long long LL ;
int n, dis[N][N], minn[N];
bool point[N]; int prim(){
point[] = true;
int ans = ;
zero(minn);zero(point);
for(int i = ; i <= n; i++) minn[i] = dis[][i];
for(int i = ; i <= n; i++){
int k = ; int mi =INF;
for(int j = ; j <= n; j++){
if(!point[j] && minn[j] <mi){
mi = minn[j];
k = j;
}
}
ans += minn[k];
point[k] = true;
for(int s = ; s <= n; s++){
if(!point[s] && dis[k][s] <minn[s])
minn[s] = dis[k][s];
}
}
return ans;
} int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
while(~scanf("%d", &n) && n){
zero(dis);
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
scanf("%d", &dis[i][j]);
}
}
printf("%d\n", prim());
}
return ;
}
题意：求最小生成树；
思路：prim + BFS
这题的难点在于寻找邻接矩阵；
用BFS 找到各点间的最小距离的点；
然后就是套模板；