Building Roads
Time Limit: 1000MS | | Memory Limit: 65536K |
Total Submissions: 13247 | | Accepted: 3661 |
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
Source
USACO 2007 December Silver
题意:
n个点的坐标,m已经建成的路,问你为使该图连通,最少还需要连接总长度为多少的边?
分析:
算出任意两点间的距离,得到一个完全图,求最小生成树即可.已经连接上的边长度为0.用kruskal算法.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
struct Node{
double x,y;
}node[N];
struct Edge{
int x,y;
double dis;
Edge(){}
Edge(int x,int y,double dis):x(x),y(y),dis(dis){}
}edge[N*1000];
bool cmp(Edge a,Edge b)
{
if(a.dis==b.dis)
return a.x<b.x;
else
return a.dis<b.dis;
}
int n,m;
int tot;
int father[N];
double G[N][N];
double getDis(int i,int j){
return sqrt( fabs((node[i].x-node[j].x))*fabs((node[i].x-node[j].x)) + fabs((node[i].y-node[j].y))*fabs((node[i].y-node[j].y)) );
}
int Find(int x){
if(father[x]==x)
return x;
return father[x]=Find(father[x]);
}
double mst;
int cnt=0;
void Kruskal(){
sort(edge+1,edge+tot+1,cmp);
for(int i=1;i<=tot;++i){
int x=Find(edge[i].x);
int y=Find(edge[i].y);
if(x!=y){
father[x]=y;
mst+=edge[i].dis;
cnt++;
if(cnt==n-1)
break;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&node[i].x,&node[i].y);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
double temp=getDis(i,j);
edge[++tot].x=i;
edge[tot].y=j;
edge[tot].dis=temp;
}
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
edge[++tot].x=x;
edge[tot].y=y;
edge[tot].dis=0;
}
Kruskal();
printf("%.2f",mst);
return 0;
}
标签:Building,node,输出精度,int,3625,tot,edge,include,dis From: https://blog.51cto.com/u_14932227/6041845