题目：
Flatopia岛国完全平坦。不幸的是，Flatopia的公共高速公路系统非常糟糕。弗拉托利亚政府意识到了这个问题，并且已经建造了一些连接一些最重要城镇的高速公路。但是，仍有一些城镇无法通过高速公路抵达。有必要建造更多的高速公路，以便能够在不离开高速公路系统的情况下在任何一对城镇之间行驶。
Flatopian城镇的编号从1到N，城镇i的位置由笛卡尔坐标（xi，yi）给出。每条高速公路连接两个城镇。所有高速公路（原始高速公路和要建造的高速公路）都遵循直线，因此它们的长度等于城镇之间的笛卡尔距离。所有高速公路都可以在两个方向使用。高速公路可以自由地相互交叉，但司机只能在位于两条高速公路尽头的小镇的高速公路之间切换。
Flatopian政府希望最大限度地降低建设新高速公路的成本。但是，他们希望保证每个城镇都可以从其他城镇到达公路。由于Flatopia是如此平坦，高速公路的成本总是与其长度成正比。因此，最便宜的高速公路系统将是最小化总公路长度的系统。
Input
输入包括两部分。第一部分描述了该国的所有城镇，第二部分描述了所有已建成的高速公路。
输入文件的第一行包含一个整数N（1 <= N <= 750），表示城镇数量。接下来的N行每行包含两个整数，xi和yi由空格分隔。这些值给出了第i个城镇的坐标（对于i从1到N）。坐标的绝对值不超过10000.每个城镇都有一个独特的位置。
下一行包含单个整数M（0 <= M <= 1000），表示现有高速公路的数量。接下来的M行每行包含一对由空格分隔的整数。这两个整数给出了一对已经通过高速公路连接的城镇号码。每对城镇至少由一条高速公路连接。
Output
为每条新高速公路写一条输出线，以便连接所有城镇，尽可能减少新高速公路的总长度。每条高速公路都应该通过打印这条高速公路连接的城镇号码来展示，并以空间隔开。
如果不需要建立新的高速公路（所有城镇都已连接），则应创建输出文件，但应该为空。
Sample Input
9 1 5 0 0 3 2 4 5 5 1 0 4 5 2 1 2 5 3 3 1 3 9 7 1 2
Sample Output
1 6 3 7 4 9 5 7 8 3
解题思路：给定n 个点的坐标，然后又给m个边表示该两个点已经连接起来不需要再建立高速公路。这个题考察的是Prim最短生成树算法，不过该题不是让我们求的是最短总距离，而是求出每一次所建立的边，既头结点和当前结点。
Code:
#include<stdio.h> #include<string.h> #include<math.h> struct node { int x; int y; }q[2000]; int e[2000][2000],book[5000],dis[50000],f[50000];//f[]是记录头结点的 int inf=999999999; int count,sum; int main() { int i,j,k,min,n,m,b,t1,t2; while(scanf("%d",&n)!=EOF) { count=0; memset(book,0,sizeof(book)); memset(dis,0,sizeof(dis)); memset(f,0,sizeof(f));//数组清零 for(i=1;i<=n;i++) scanf("%d%d",&q[i].x,&q[i].y); scanf("%d",&m); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) e[i][j]=e[j][i]=((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y)); for(i=1;i<=m;i++) { scanf("%d%d",&t1,&t2);//已经建立的点就让两点之间距离的边为0 e[t1][t2]=e[t2][t1]=0; } for(i=1;i<=n;i++) f[i]=1;//初始让所有头结点都为 1 for(i=1;i<=n;i++) dis[i]=e[1][i]; book[1]=1; count++; while(count<n) { min=inf; for(i=1;i<=n;i++) { if(book[i]==0&&dis[i]<min) { min=dis[i]; j=i; } } book[j]=1; count++; if(e[f[j]][j]!=0)//输出要建立所要建立边的两点 printf("%d %d\n",f[j],j); for(k=1;k<=n;k++) { if(book[k]==0&&dis[k]>e[j][k]) { dis[k]=e[j][k]; f[k]=j;//更新头结点 } } } } return 0; }
注意：题中的样例给出是随机的，也就是说求得的样例只要所对应的边一样就行了。
