由于题目简单，部分题意写在代码中（简单题就应该多练英文...），且较少给注释，需要注意的地方会写在代码中，虽然四个题意各有千秋，但万变不离其宗，细细思考一番会发现四道题都属于很直接的最小生成树问题，由于博主时间原因，暂提供Kruskal解法。
这四题可以作为最小生成树（MST）入门的上手题库。
POJ1251(ZOJ1406)-Jungle Roads
//Kruskal-裸
//POJ1251-ZOJ1406
//找出维护道路的最小费用
//Time:0Ms Memory:168K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; #define MAXN 28
#define MAXM 80 struct Edge {
int u, v;
int d;
friend bool operator < (Edge e1, Edge e2) { return e1.d < e2.d; }
}e[MAXM]; int n, m;
int fa[MAXN]; int Find(int x)
{
return fa[x] < ? x : fa[x] = Find(fa[x]);
} void Union(int r1,int r2)
{
int num = fa[r1] + fa[r2];
if (r1 < r2)
{
fa[r2] = r1;
fa[r1] = num;
}
else {
fa[r1] = r2;
fa[r2] = num;
}
} void kruskal()
{
int num = ;
int minroad = ;
memset(fa, -, sizeof(fa));
for (int i = ; i < m; i++)
{
int r1 = Find(e[i].u);
int r2 = Find(e[i].v);
if (r1 == r2) continue;
minroad += e[i].d;
Union(r1, r2);
if (++num == n - ) break;
}
printf("%d\n", minroad);
} int main()
{
while (scanf("%d", &n), n)
{
m = ;
for (int i = ; i < n; i++)
{
int road;
char city[];
scanf("%s%d", city, &road); //用%c和getchar()会RE，可能是后台数据的问题
while (road--)
{
int d;
char c[];
scanf("%s%d", c, &d);
e[m].u = city[] - 'A';
e[m].v = c[] - 'A';
e[m++].d = d;
}
}
sort(e, e + m);
kruskal();
}
return ;
}
POJ1287(ZOJ1372)-Networking
//Kruskal-须查重边
//设计一个由给定所需网线长度的网络组成的最短网线方案(可能有重边)
//POJ1287-ZOJ1372
//Time:16Ms Memory:192K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; #define MAXN 51 struct Edge {
int u, v;
int d;
friend bool operator < (Edge e1, Edge e2) { return e1.d < e2.d; }
}e[MAXN*MAXN]; int n, m;
int fa[MAXN];
int v[MAXN][MAXN]; //端点查边
int minroad; int Find(int x)
{
return fa[x] < ? x : fa[x] = Find(fa[x]);
} void Union(int r1, int r2)
{
int num = fa[r1] + fa[r2];
if (r1 < r2)
{
fa[r2] = r1;
fa[r1] = num;
}
else {
fa[r1] = r2;
fa[r2] = num;
}
} void kruskal()
{
int num = ;
minroad = ;
memset(fa, -, sizeof(fa));
for (int i = ; i < m; i++)
{
int r1 = Find(e[i].u);
int r2 = Find(e[i].v);
if (r1 == r2) continue;
Union(r1, r2);
minroad += e[i].d;
if (++num == n - ) break;
}
printf("%d\n", minroad);
} int main()
{
while (scanf("%d", &n), n)
{
memset(v, -, sizeof(v));
scanf("%d", &m);
for (int i = ; i < m; i++)
{
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].d);
if (v[e[i].u][e[i].v] >= ) //查重
{
e[v[e[i].u][e[i].v]].d = min(e[v[e[i].u][e[i].v]].d, e[i].d);
i--; m--;
}
else v[e[i].u][e[i].v] = i;
}
sort(e, e + m);
kruskal();
}
return ;
}
POJ2031(ZOJ1718)-Jungle Roads
//Kruskal+去重叠+简单几何
//题目不难，如果用到并查集，那么去重的部分需要考虑好
//Time:32Ms Memory:268K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std; #define MAXN 105
#define POW2(x) ((x)*(x))
#define DIS(i,j) (sqrt(POW2(v[i].x - v[j].x) + POW2(v[i].y - v[j].y) + POW2(v[i].z - v[j].z))) struct Vertex {
double x, y, z;
double r;
}v[MAXN]; struct Edge {
int u, v;
double d;
friend bool operator < (Edge e1, Edge e2) { return e1.d < e2.d; }
}e[MAXN*MAXN]; int n, m;
int fa[MAXN]; int Find(int x)
{
return fa[x] < ? x : fa[x] = Find(fa[x]);
} void Union(int r1, int r2)
{
r1 = Find(r1);
r2 = Find(r2);
if (r1 == r2) return; //处理边的时候需要考虑，否则将RE
int num = fa[r1] + fa[r2];
if (r1 < r2)
{
fa[r2] = r1;
fa[r1] = num;
}
else {
fa[r1] = r2;
fa[r2] = num;
}
} void kruskal()
{
int num = ;
double minroad = ;
for (int i = ; i < m; i++)
{
int r1 = Find(e[i].u);
int r2 = Find(e[i].v);
if (r1 == r2) continue;
Union(r1, r2);
minroad += e[i].d;
if (++num == n - ) break;
}
printf("%.3lf\n", minroad);
} int main()
{
while (scanf("%d", &n), n)
{
m = ;
memset(fa, -, sizeof(fa));
for (int i = ; i < n; i++)
{
scanf("%lf%lf%lf%lf", &v[i].x, &v[i].y, &v[i].z, &v[i].r);
for (int j = ; j < i; j++)
{
double len = DIS(i, j) - v[i].r - v[j].r;
if (len <= 1e-)
Union(i, j); //可能r1与r2同集合-在Union中处理
else {
e[m].u = i;
e[m].v = j;
e[m++].d = len;
}
}
}
sort(e, e + m);
kruskal();
}
return ;
}
POJ2421-Jungle Roads
//Kruskal-略变形
//Time:47Ms Memory:272K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 105 struct Edge {
int u, v;
int d;
friend bool operator < (Edge e1, Edge e2) { return e1.d < e2.d; }
}e[MAX*MAX/]; int n, m;
int fa[MAX];
int d[MAX][MAX]; int Find(int x)
{
return fa[x] < ? x : fa[x] = Find(fa[x]);
} void Union(int r1, int r2)
{
r1 = Find(r1);
r2 = Find(r2);
if (r1 == r2) return;
int num = fa[r1] + fa[r2];
if (fa[r1] < fa[r2])
{
fa[r2] = r1;
fa[r1] = num;
}
else {
fa[r1] = r2;
fa[r2] = num;
}
} void kruskal()
{
int minroad = ;
int num = ;
for (int i = ; i < m; i++)
{
int r1 = Find(e[i].u);
int r2 = Find(e[i].v);
if (r1 == r2) continue;
Union(r1, r2);
minroad += e[i].d;
if (++num == n - ) break;
}
printf("%d\n", minroad);
} int main()
{
memset(fa, -, sizeof(fa));
scanf("%d", &n);
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
scanf("%d", &d[i][j]);
int k;
scanf("%d", &k);
while (k--)
{
int u, v;
scanf("%d%d", &u, &v);
Union(u, v);
}
m = ;
for (int i = ; i <= n; i++)
for (int j = ; j < i; j++)
{
e[m].u = i;
e[m].v = j;
e[m++].d = d[i][j];
}
sort(e, e + m);
kruskal();
return ;
}