題意:給出一個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
