| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 11861 | Accepted: 3376 |
Description
Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.
Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Two space-separated integers: Xi and Yi
* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.
Output
* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.
Sample Input
4 1
1 1
3 1
2 3
4 3
1 4
Sample Output
4.00
一个最小生成树问题，kruskal算法会TLE
没什么可说i的，这玩意得存模板，这题唯一的不一样只是改变了权值为两点间距。
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
struct node
{
double x,y;
}a[1005];
int vis[1005];
double d[1005][1005];
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double prim()
{
memset(vis,0,sizeof(vis));
double low[1005];
int pos=1;
double ans=0;
vis[1]=1;
for(int i=2;i<=n;i++){
low[i]=d[pos][i]; }
for(int i=1;i<n;i++){
double min=INF;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&min>low[j]){
min=low[j];
pos=j;
}
}
vis[pos]=1;
ans+=min;
for(int i =1;i<=n;i++)
{
if(!vis[i]&&low[i]>d[pos][i]){
low[i]=d[pos][i];
}
}
}
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(d,INF,sizeof(d));
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
}
for(int i=1;i<=n;i++){
for(int j =i+1;j<=n;j++){
d[i][j]=d[j][i]=dis(a[i],a[j]);
}
}
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
d[x][y]=0;
d[y][x]=0;
}
printf("%.2f\n",prim());
}
}