luogu2872 [USACO07DEC]道路建设Building Roads

luogu2872 [USACO07DEC]道路建设Building Roads

​​ 题目描述

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.

给出nn个点的坐标,其中一些点已经连通,现在要把所有点连通,求修路的最小长度.

输入输出格式

输入格式：

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. 输出格式：

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. 输入输出样例

输入样例#1：

4 1 1 1 3 1 2 3 4 3 1 4 输出样例#1：

4.00 这题本来写的是prim 因为大约n^2复杂度嘛 然后因为 写完之后发现把点都打上标记走不过去了，答案错误 于是使用kruscal(prim也可以做 我把相连的两边的权值改成了0这样建立生成树的时候一定存在我这样的边 偷偷看了下zhx的代码 发现直接在读入的时候给他们先都扔进同一个并查集就好了

#include#include#include#define N 1100#define ll long longusing namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}double ans;int x[N],y[N],n,m,fa[N],num,h[N];struct node{ int x,y,next;ll z;}data[2*N*N];inline ll calc(int st,int to){ return (ll)(x[st]-x[to])*(x[st]-x[to])+(ll)(y[st]-y[to])*(y[st]-y[to]);}inline bool cmp(node a,node b){return a.z

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。