题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1048
题意：N个城镇之间已有M条高速公路，问还需建哪几条高速公路使所有的城镇都相通，并且路程最短。
——>>这道题与zoj1203很是相像,不同的是这题已有互通的边。
计算任意两个town之间的距离并存起来，排序，并查并记录要连的边。处理输出顺序，在这里，可能前面的处理方法与标程不一样，搞得现在处理输出顺序挺麻烦，
如果要输出1 2， 3 7， 3 8， 3 9， 4 5， 4 9 的话，应该按这样的顺序输出：1 2， 3 7， 4 5， 8 3， 9 3， 9 4。
#include <iostream>
#include <cmath>
#include <algorithm>using namespace std;const int maxn = 1000 + 10; //最多有1000条已有通路（750个towns也足够了）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;
}bool cmpp(node e1, node e2) //定义排序方式，按编号从小到大排
{if(e1.x != e2.x)return e1.x < e2.x;elsereturn e1.y < e2.y;
}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，说明这两个towns已相连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}
}cdis dist[maxn*maxn]; //用来存任意两点间的距离
node load[maxn*maxn]; //用来保存需要连调整公路的两个城市int main()
{int N, i, j, T, M, a[maxn], b[maxn];node map[maxn]; //输入的N个结点（N个towns的坐标）cin>>T;while(T--){cin>>N;for(i = 0; i < N; i++) //输入N个点的坐标，存到map里cin>>map[i].x>>map[i].y;cin>>M;for(i = 0; i < M; i++)cin>>a[i]>>b[i];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（因为只有它自己）}for(i = 0; i < M; i++)judge(a[i]-1, b[i]-1);int cnt = 0; //cnt用来记数需要连多少条高速公路for(i = 0; i < m; i++) //对m个距离进行扫描{int ok = judge(dist[i].n1, dist[i].n2); //判断这两个点是否在同一棵树中if(!ok) //如果不在同一棵树中的话，把它们连在同一棵树中{if(dist[i].n1 > dist[i].n2) //记录到load数组里，保证两个城市的编号前者小、后者大{load[cnt].x = dist[i].n2;load[cnt++].y = dist[i].n1;}else{load[cnt].x = dist[i].n1;load[cnt++].y = dist[i].n2;}}}sort(load, load+cnt, cmpp); //按town的编号排序int min_val = load[0].x; //以下是用来处理输出的，min_val用来保存相同编号，标准值for(i = 1; i < cnt; i++){if(load[i].x == min_val) //如果发现后一个结点与前一个结点的第一个town的编号相同，则交换第一个town与第二个town的位置{int temp = load[i].x;load[i].x = load[i].y;load[i].y = temp;}else min_val = load[i].x; //更新标准值}sort(load, load+cnt, cmpp); //再排一次序for(i = 0; i < cnt; i++)cout<<load[i].x+1<<" "<<load[i].y+1<<endl; //数组中的编号从0开始的，故+1输出if(T) cout<<endl; //空行}return 0;
}