POJ 1751 Highways 最小生成树

题意:给出一个N，代表N个小镇。
接下来N行每行一个坐标(x,y)代表第i个小镇的坐标。
再给出一个M，代表已经修好了几条路，接下来M行，每行2个数（i,j）代表第i个小镇和第j个小镇是有路的。
问你最少还要修多少条路，并把每条路连接的两个小镇输出来。
因为是spj，所以就输出的时候就没管顺序了。 www.2cto.com
这道题一看就知道是纯MST，我也顺手就做了。交了20次左右，各种TLE，终于被我A了~~然后又试了10次，发现一个超神奇的事情。。。
[cpp]
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string> 
#include <cmath> 
#include <cstring> 
#include <queue> 
#include <set> 
#include <stack> 
#include <map> 
#define Max 20005 
struct node 
{ 
    int x,y; 
    double len; 
} line[570000]; 
struct node1 
{ 
    int x,y; 
} road[800]; 
bool cmp(node &x,node &y)//注意这个 
{ 
    return x.len<y.len; 
} 
int f[570000]; 
int find(int x) 
{ 
    if(f[x]==x) 
        return x; 
    else 
        return f[x]=find(f[x]); 
} 
double getdis(node1 &x,node1 &y)//和这个。。 
{ 
    return sqrt((double)(x.x-y.x)*(x.x-y.x)+(double)(x.y-y.y)*(x.y-y.y)); 
} 
void merge(int x,int y) 
{ 
    x=find(x); 
    y=find(y); 
    f[y]=x; 
} 
using namespace std; 
int main() 
{ 
    int i,j,l,n,m; 
    int x,y,s; 
    int q; 
    cin>>n; 
    node1 test; 
    int k=0; 
    int sum=0; 
    for(i=1; i<=n; i++) 
    { 
        scanf("%d%d",&road[i].x,&road[i].y); 
    } 
    cin>>q; 
    for(i=0; i<=570000; i++) 
        f[i]=i; 
    for(i=0; i<q; i++) 
    { 
        scanf("%d%d",&x,&y); 
        merge(x,y); 
    } 
    for(i=1; i<=n; i++) 
    { 
        for(j=i+1; j<=n; j++) 
        { 
            if(find(i)!=find(j)) 
            { 
                line[k].x=i; 
                line[k].y=j; 
                line[k].len=getdis(road[i],road[j]); 
                k++; 
            } 
        } 
    } 
    int num=0; 
    sort(line,line+k,cmp); 
    for(i=0; i<k; i++) 
    { 
        int a=find(line[i].x); 
        int b=find(line[i].y); 
        if(a!=b) 
        { 
            f[b]=a; 
            num++; 
            printf("%d %d/n",line[i].x,line[i].y); 
        } 
        if(num>=n-1)break; 
    } 
    return 0; 
} 
[cpp] 
想必都看到我写注释的哪两个地方了。。。一开始我写的排序是 
bool cmp(node x,node y) 
{ 
    return x.len<y.len; 
} 
下面那个函数也是没有加&。 
然后就TLE了。。我把主程序至少大改小改10来次。还是TLE。 
突然想起来这个排序和计算距离的函数才是用时最多的。所以就改了这两处。。没想到就A了。 
1751    Accepted    6860K   1000MS  C++ 1674B//没加 
1751    Accepted    6856K   641MS   C++ 1678B//加了 
虽然是600MS。但是也充分说明问题了。 
当然这个用时还是很多。。继续优化。。 
最后，做题要更加仔细！
作者：kdqzzxxcc