四道MST，适合Prim解法，也可以作为MST练习题。
题意包括在代码中。
POJ1258-Agri Net
水题
//Prim-没什么好说的
//接受一个邻接矩阵，求MST
//Time:0Ms Memory:220K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 105
#define INF 0x3f3f3f3f
int n, m;
int d[MAX][MAX];
int lowcost[MAX];
bool v[MAX];
void prim()
{
int minroad = ;
memset(v, false, sizeof(v));
v[] = true;
for (int i = ; i < n; i++)
lowcost[i] = d[i][];
for (int i = ; i < n; i++)
{
double mind = INF;
int k;
for (int j = ; j < n; j++)
{
if (!v[j] && mind > lowcost[j])
{
mind = lowcost[j];
k = j;
}
} minroad += lowcost[k];
v[k] = true;
for (int j = ; j < n; j++)
if (!v[j]) lowcost[j] = min(d[k][j], lowcost[j]);
}
printf("%d\n", minroad);
}
int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i < n; i++)
for (int j = ; j < n; j++)
scanf("%d", &d[i][j]);
prim();
}
return ;
}
POJ1751(ZOJ2048)-Highways
//Prim-好题
//ZOJ2048-POJ1751
//ZOJ中多组样例，两个样例间有一个空格(否则会WA)
//需要记录上一个节点-注意内存限制在10^4K内
//有M个城市已经有通路，输出让N个城市生成最短通路的各边，Special Judge-输出次序不定
//Time:94Ms Memory:4648K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std; #define MAX 755
#define INF 0x3f3f3f3f
#define POW2(x) ((x)*(x))
#define DIS(i,j) (sqrt(POW2(p[i][0] - p[j][0]) + POW2(p[i][1] - p[j][1]))) int n, m;
double p[MAX][];
int fa[MAX]; //记录上一个顶点
double d[MAX][MAX];
double lowcost[MAX];
bool v[MAX]; void prim()
{
memset(v, false, sizeof(v));
v[] = true;
for (int i = ; i <= n; i++)
{
lowcost[i] = d[i][];
fa[i] = ;
}
for (int i = ; i <= n; i++)
{
double mind = INF;
int k;
for (int j = ; j <= n; j++)
{
if (!v[j] && mind > lowcost[j])
{
mind = lowcost[j];
k = j;
}
}
if (mind > 1e-)
printf("%d %d\n", fa[k], k); v[k] = true;
for (int j = ; j <= n; j++)
{
if (!v[j] && lowcost[j] > d[k][j])
{
lowcost[j] = d[k][j];
fa[j] = k;
}
}
}
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%lf%lf", &p[i][], &p[i][]);
for (int j = ; j < i; j++)
d[i][j] = d[j][i] = DIS(i, j);
}
scanf("%d", &m);
for (int i = ; i < m; i++)
{
int v1, v2;
scanf("%d%d", &v1, &v2);
d[v1][v2] = d[v2][v1] = ;
}
prim();
return ;
}
POJ2349(ZOJ1914)-Arctic Network
//Prim
//POJ2349-ZOJ1914
//有n个前哨可以通过卫星通信(无距离限制)，总共m个前哨，相互通信可以通过无线电通信(有距离限制),求所需无线电信号最短距离
//定理：如果去掉所有权值大于d的边后，最小生成树被分割成为k个连通支，图也被分割成为k个连通支(可尝试证明)
//Time:47Ms Memory:2164K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std; #define MAX 501
#define INF 0x3f3f3f3f
#define POW2(x) ((x)*(x))
#define DIS(i,j) (sqrt(POW2(p[i][0] - p[j][0]) + POW2(p[i][1] - p[j][1]))) int n, m;
double p[MAX][]; //point
double d[MAX][MAX]; //distance
double lowcost[MAX];
bool v[MAX]; void prim()
{
memset(lowcost, , sizeof(lowcost));
memset(v, false, sizeof(v));
v[] = true;
for (int i = ; i < m; i++)
lowcost[i] = d[i][];
for (int i = ; i < m; i++)
{
int mind = INF;
int k;
for (int j = ; j < m; j++)
{
if (!v[j] && mind > lowcost[j])
{
mind = lowcost[j];
k = j;
}
}
v[k] = true;
for (int j = ; j < m; j++)
if(!v[j]) lowcost[j] = min(d[k][j], lowcost[j]);
}
} int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = ; i < m; i++)
{
scanf("%lf%lf", &p[i][], &p[i][]);
for (int j = ; j < i; j++)
d[i][j] = d[j][i] = DIS(i, j);
} prim();
sort(lowcost, lowcost + m);
printf("%.2lf\n", lowcost[m - n]);
//G++需要使用printf("%.2f\n", lowcost[m-n]);
//原因查了半天，好像是因为新版GCC标准中将%f和%lf合并为%f的意思
}
return ;
}
POJ3026-Borg Maze
//Prim+BFS
//总是心想着要创造一个新算法，结果越想越麻烦...
//保险做法:找出每个点间的距离，再进行Prim
//Time:79Ms Memory:292K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std; #define MAX 125 //MAX 50的话会RE或WA(博主在55RE，在100WA) struct Point{
int x, y;
int step;
}p; int r, c;
char board[MAX][MAX];
int d[MAX][MAX];
int num[MAX][MAX], cnt;
int lowcost[MAX];
bool v[MAX][MAX];
int mov[][] = { {,}, {-,}, {,}, {,-} }; void bfs(Point p)
{
memset(v, false, sizeof(v));
v[p.x][p.y] = true;
int np = num[p.x][p.y];
queue<Point> q;
p.step = ;
q.push(p);
while (!q.empty())
{
Point cur = q.front();
q.pop();
for (int i = ; i < ; i++)
{
Point t = cur;
t.x += mov[i][];
t.y += mov[i][];
if (t.x > && t.y > && t.x < r && t.y < c && !v[t.x][t.y])
{
if (board[t.x][t.y] == '#') continue;
int nt = num[t.x][t.y];
t.step++;
v[t.x][t.y] = true;
if (board[t.x][t.y] == 'A' || board[t.x][t.y] == 'S')
d[nt][np] = t.step;
q.push(t);
}
}
}
} void prim()
{
int v[MAX];
memset(v, false, sizeof(v));
memset(lowcost, 0x3f, sizeof(lowcost));
v[] = true;
for (int i = ; i < cnt; i++)
lowcost[i] = d[i][]; int minv = ;
for (int i = ; i < cnt; i++)
{
int mind = 0x3f3f3f3f;
int k;
for (int j = ; j < cnt; j++)
{
if (!v[j] && mind > lowcost[j])
{
mind = lowcost[j];
k = j;
}
}
minv += mind;
v[k] = true;
for (int j = ; j < cnt; 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--)
{
cnt = ;
scanf("%d%d", &c, &r);
gets_s(board[]);
for (int i = ; i < r; i++)
{
gets_s(board[i], MAX);
for (int j = ; j < c; j++)
if (board[i][j] == 'S' || board[i][j] == 'A')
num[i][j] = cnt++;
}
for (int i = ; i < r; i++)
for (int j = ; j < c;j++)
if (board[i][j] == 'S' || board[i][j] == 'A')
{
p.x = i; p.y = j;
bfs(p);
}
prim();
}
return ;
}