POJ 1751 Highways 最小生成树 - c++编程基础

题意:给出一个N，代表N个小镇。
接下来N行每行一个坐标(x,y)代表第i个小镇的坐标。
再给出一个M，代表已经修好了几条路，接下来M行，每行2个数（i,j）代表第i个小镇和第j个小镇是有路的。
问你最少还要修多少条路，并把每条路连接的两个小镇输出来。
因为是spj，所以就输出的时候就没管顺序了。 www.2cto.com
这道题一看就知道是纯MST，我也顺手就做了。交了20次左右，各种TLE，终于被我A了~~然后又试了10次，发现一个超神奇的事情。。。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 }
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 {
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 {
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 }
下面那个函数也是没有加&。
然后就TLE了。。我把主程序至少大改小改10来次。还是TLE。
突然想起来这个排序和计算距离的函数才是用时最多的。所以就改了这两处。。没想到就A了。
1751 Accepted 6860K 1000MS C++ 1674B//没加
1751 Accepted 6856K 641MS C++ 1678B//加了
虽然是600MS。但是也充分说明问题了。
当然这个用时还是很多。。继续优化。。
最后，做题要更加仔细！
作者：kdqzzxxcc