题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1203
题意：求连通n个城市的最短路径。
——>>先把“任意”两点间的距离存到dist数组里，然后对其进行一次排序，接着开始对dist进行扫描，
如果扫描的两个点的树根相同，说明这两个城市已经相连，就不用加距离了，如果扫描到的两个点的树根不相同，
说明这两个城市还没有相连，sum要加上这个距离，最后输出sum即可。
带路径压缩：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>using namespace std;const int maxn = 100 + 10; //最多有100个城市typedef struct Tnode //定义点类型
{double x;double y;
}node;typedef struct Tdistance //定义距离类型，同时保存下是点map[n1]与点map[n2]之间的距离
{int n1;int n2;double dis;
}cdis;bool cmp(cdis d1, cdis d2) //定义排序方式，按间距从小到大的方式排
{return d1.dis < d2.dis;
}int fa[maxn]; //fa为结点的父亲，height为结点的高度int find(int x) //返回结点x的根（是map中的编号）
{return fa[x] == x ? x : (fa[x] = find(fa[x]));
}bool judge(int x, int y) //判断、合并操作
{int new_x = find(x);int new_y = find(y);if(new_x == new_y) return 1; //如果编号为x与编号为y的结点已在同一棵树中，返回1，说明这两个城市已相连fa[new_y] = new_x;return 0;
}int main()
{int N, i, j;node map[maxn]; //输入的N个结点（N个城市的坐标）cdis dist[maxn*maxn]; //用来存任意两点间的距离int cnt = 1, first = 1; //cnt用来计数测试数据组数，first为输出标记while(cin>>N){if(N == 0) return 0; //当N为0时，返回for(i = 0; i < N; i++) //输入N个点的坐标，存到map里cin>>map[i].x>>map[i].y;int m = 0; //m用来统计多少个两点间的距离（存map[i]与map[j]之间的距离，就不存map[j]与map[i]之间的距离）for(i = 0; i < N; i++)for(j = i+1; j < N; j++){dist[m].n1 = i; //记录下结点map[i]的编号dist[m].n2 = j; //记录下结点map[j]的编号dist[m++].dis = sqrt(pow(map[i].x - map[j].x, 2) + pow(map[i].y - map[j].y, 2)); //计算两点间的距离}sort(dist, dist+m, cmp); //排序for(i = 0; i < N; i++) fa[i] = i; //建N棵根树,初始化树根为其本身double sum = 0; //连接各城市的总距离for(i = 0; i < m; i++) //对m个距离进行扫描{int ok = judge(dist[i].n1, dist[i].n2); //判断这两个点是否在同一棵树中if(!ok) //如果不在同一棵树中的话，把它们连在同一棵树中，距离加上sum += dist[i].dis;}if(first) first = !first; //让第一组数据不输出空行，下面的测试数据输出空行else cout<<endl;cout<<"Case #"<<cnt++<<":"<<endl;cout<<"The minimal distance is: "<<setiosflags(ios::fixed)<<setprecision(2)<<sum<<endl;}return 0;
}
容易理解小小的写法：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>using namespace std;const int maxn = 100 + 10; //最多有100个城市typedef struct Tnode //定义点类型
{double x;double y;
}node;typedef struct Tdistance //定义距离类型，同时保存下是点map[n1]与点map[n2]之间的距离
{int n1;int n2;double dis;
}cdis;bool cmp(cdis d1, cdis d2) //定义排序方式，按间距从小到大的方式排
{return d1.dis < d2.dis;
}int fa[maxn], height[maxn]; //fa为结点的父亲，height为结点的高度int find(int x) //返回结点x的根（是map中的编号）
{while(fa[x] != x){x = fa[x];}return x;
}bool judge(int x, int y) //判断、合并操作
{int fx = find(x);int fy = find(y);if(fx == fy) //如果编号为x与编号为y的结点已在同一棵树中，返回1，说明这两个城市已相连return 1;else //否则{if(height[fx] > height[fy]) //当编号为x的结点所在树的高度>编号为y的结点所在树的高度时fa[fy] = fx; //把fx设为fy的父亲else if(height[fx] == height[fy]) //当编号为x的结点所在树的高度==编号为y的结点所在树的高度时{fa[fy] = fx; //把fx设为fy的父亲height[fx]++; //同时把树fx的高度+1}else //当编号为x的结点所在树的高度<编号为y的结点所在树的高度时fa[fx] = fy; //把fy设为fx的父亲return 0; //返回0}
}int main()
{int N, i, j;node map[maxn]; //输入的N个结点（N个城市的坐标）cdis dist[maxn*maxn]; //用来存任意两点间的距离int cnt = 1, first = 1; //cnt用来计数测试数据组数，first为输出标记while(cin>>N){if(N == 0) return 0; //当N为0时，返回for(i = 0; i < N; i++) //输入N个点的坐标，存到map里cin>>map[i].x>>map[i].y;int m = 0; //m用来统计多少个两点间的距离（存map[i]与map[j]之间的距离，就不存map[j]与map[i]之间的距离）for(i = 0; i < N; i++)for(j = i+1; j < N; j++){dist[m].n1 = i; //记录下结点map[i]的编号dist[m].n2 = j; //记录下结点map[j]的编号dist[m++].dis = sqrt(pow(map[i].x - map[j].x, 2) + pow(map[i].y - map[j].y, 2)); //计算两点间的距离}sort(dist, dist+m, cmp); //排序for(i = 0; i < N; i++) //建N棵根树{fa[i] = i; //初始化树根为其本身height[i] = 1; //初始化树高为1（因为只有它自己）}double sum = 0; //连接各城市的总距离for(i = 0; i < m; i++) //对m个距离进行扫描{int ok = judge(dist[i].n1, dist[i].n2); //判断这两个点是否在同一棵树中if(!ok) //如果不在同一棵树中的话，把它们连在同一棵树中，距离加上sum += dist[i].dis;}if(first) first = !first; //让第一组数据不输出空行，下面的测试数据输出空行else cout<<endl;cout<<"Case #"<<cnt++<<":"<<endl;cout<<"The minimal distance is: "<<setiosflags(ios::fixed)<<setprecision(2)<<sum<<endl;}return 0;
}