对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。
普里姆算法是以其中某一顶点为起点，逐步寻找各个顶点上最小权值的边来构建最小生成树。
其中运用到了回溯，贪心的思想。
----------2018年5月24日补：
#begin
根据定义我们可知，求一个图的最小生成树的时候，一定会将所有的点都连接起来，也就是说，我们从任何一个点出发都可以得到这个图的最小生成树，那么我这里暂定从0出发，寻找到和0相连的点中最小的权值，作为连接0这一个点的边（如果有相同的最小权值，则视要求处理），将0这一个点设置为不可访问，同时保存此时的连接点，将求到的这一个点做和0一样相同的处理...处理出n个点就可以求得这个图的最小生成树了（如果不能处理出n个点，那么此图的最小生成树也就不存在）。
#end
废话少说，直接上题吧！这些东西多练就好！
一、最小生成树：
题目描述
求一个连通无向图的最小生成树的代价（图边权值为正整数）。
输入
第 一行是一个整数N（1<=N<=20），表示有多少个图需要计算。以下有N个图，第i图的第一行是一个整数M（1<=M& lt;=50），表示图的顶点数，第i图的第2行至1+M行为一个M*M的二维矩阵，其元素ai,j表示图的i顶点和j顶点的连接情况，如果 ai,j=0，表示i顶点和j顶点不相连；如果ai,j>0，表示i顶点和j顶点的连接权值。
输出
每个用例，用一行输出对应图的最小生成树的代价。
样例输入
1
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
样例输出
15
//Asimple
#include <stdio.h>
#include <iostream>
#include <string.h> using namespace std;
#define INF 0xffffff
const int maxn = 55;
int G[maxn][maxn];//建图
int T, n; int prim()
{
int Min, sum = 0;
int adv[maxn]; //保存定点下标
int lowc[maxn]; //保存权值 adv[0] = lowc[0] = 0 ;
//初始化
for(int i=1; i<n; i++)
{
lowc[i] = G[0][i];//先放入 第0行 的所有权值
adv[i] = 0 ;
} //构建过程
for(int i=1; i<n; i++)
{
Min = INF ;
int j = 1 ;
int k = 0 ; while( j < n )
{
if( lowc[j]!=0 && lowc[j]<Min)
{
Min = lowc[j] ;
k = j ;
}
j ++ ;
}
sum += G[adv[k]][k] ;//计算最小权值
//printf("%d,%d",adv[k],k);//打印节点
lowc[k] = 0 ; //逐行遍历接下来的k个顶点
for(int l=1; l<n; l++)
{
if( lowc[l]!=0 && G[k][l] < lowc[l] )
{
lowc[l] = G[k][l] ;
adv[l] = k ;
}
}
}
return sum ;
} int main()
{
cin >> T ;
while( T -- )
{
cin >> n ;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
cin >> G[i][j];
if( G[i][j] == 0 && i!=j )
G[i][j] = INF ;
}
cout << prim() << endl ;
} return 0;
}
二、判断最小生成树是否唯一
题目描述
给出一个连通无向图，请判断其最小生成树是否是唯一的。
定义1（生成树）：给出一个连通无向图G=（V，E），G的一颗生成树被标记为T=（V，E），则具有以下性质：
1）V'=V；
2）T是连通无回路的。
定义2（最小生成树）：给出一个边带权的连通无向图G=（V，E），G 的最小生成树T=（v，E）是具有最小总耗费的生成树。T的总耗费表示E' 中所有边的权值的和。
输入
第 一行给出一个整数t（１＜＝ｔ＜＝２０），表示测试用例数，每个测试用例表示一个图，测试用例的第一行给出两个整数ｎ，ｍ（１＜＝ｎ＜＝１００），分别表 示顶点和边的数目，后面的ｍ行每行是一个三元组（ｘｉ，ｙｉ，ｗｉ），表示ｘｉ和ｙｉ通过权值为ｗｉ的边相连。任意两个节点间至多只有一条边相连。
输出
对于每个测试用例，如果ＭＳＴ是唯一的，输出其总耗费；否则输出字符串'Not Unique!'.
样例输入
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
样例输出
3
Not Unique!
#include <stdio.h>
#include <iostream>
#include <string.h> using namespace std;
#define INF 0xffffff
const int maxn = 55;
int G[maxn][maxn];//建图
int T, n, m, x, y, num; void prim()
{
int Min, sum = 0;
int adv[maxn]; //保存定点下标
int lowc[maxn]; //保存权值
bool flag = false ; adv[0] = lowc[0] = 0 ;
//初始化
for(int i=1; i<n; i++)
{
lowc[i] = G[0][i];//先放入 第0行 的所有权值
adv[i] = 0 ;
} //构建过程
for(int i=1; i<n; i++)
{
Min = INF ;
int j = 1 ;
int k = 0 ; while( j < n )
{
if( lowc[j]!=0 && lowc[j]<=Min)
{
if( lowc[j] == Min ) flag = true ;
Min = lowc[j] ;
k = j ;
}
j ++ ;
}
sum += G[adv[k]][k] ;//计算最小权值
lowc[k] = 0 ; //逐行遍历接下来的k个顶点
for(int l=1; l<n; l++)
{
if( lowc[l]!=0 && G[k][l] < lowc[l] )
{
lowc[l] = G[k][l] ;
adv[l] = k ;
}
}
}
if( flag ) cout << "Not Unique!" << endl ;
else cout << sum << endl ;
} int main()
{
cin >> T ;
while( T -- )
{
cin >> n >> m ;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
if( i == j ) G[i][j] = 0 ;
else G[i][j] = INF ;
}
for(int i=0; i<m; i++)
{
cin >> x >> y >> num ;
G[x-1][y-1] = num ;
G[y-1][x-1] = num ;
}
prim();
} return 0;
}
2018年4月1日更正：
上面的代码过不了 POJ 1679。谢谢指点~~ 今天更改了下自己的程序。
| 18390068 | Asimple | 1679 | Accepted | 312K | 16MS | C++ | 1483B | 2018-04-01 20:08:48 |
//Asimple
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
#define INF 0xffffff
typedef long long ll ;
const int maxn = +;
int n, T, num, cnt, x, y, t, m, w;
int Map[maxn][maxn]; void prim() {
int lowc[maxn];
for(int i=; i<=n; i++) lowc[i] = Map[][i];
int sum = ;
bool flag = false; for(int l=; l<n; l++) {
int Min = INF;
int k = ;
for(int j=; j<=n; j++) {
if( lowc[j]!= && Min > lowc[j] ) {
k = j;
Min = lowc[j];
}
}
if( Min == INF ) break;
sum += Min;
int cnt = ;
for(int i=; i<=n; i++)
if( Map[k][i] == lowc[k] )
cnt ++;
if( cnt > ) {
flag = true;
break;
}
lowc[k] = ; for(int i=; i<=n; i++) {
if( lowc[i] > Map[k][i] ) {
lowc[i] = Map[k][i];
}
}
} if( flag ) cout << "Not Unique!" << endl;
else cout << sum << endl;
} void input() {
ios_base::sync_with_stdio(false);
cin >> T;
while( T -- ) {
cin >> n >> m;
for(int i=; i<=n; i++) {
for(int j=; j<=n; j++) {
Map[i][j] = i==j?:INF;
}
}
while( m -- ) {
cin >> x >> y >> w;
Map[x][y] = min(Map[x][y], w);
Map[y][x] = Map[x][y];
}
prim();
}
} int main() {
input();
return ;
}