$P2872\ [USACO07DEC]道路建设Building\ Roads$

$problem$

错的原因是$RE$（大雾，时刻谨记 $N$ 个地方的话保守开 $\frac{N^2}{2}$ 大小。因为是边。

边最多的情况即完全图： $1+2+3+4...+n = \frac{N*(N-1)}{2} $

所以还是个板子。

忽略丑陋的$2^{18}$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

inline LL read () { LL res = 0 ;int f (1) ;char ch = getchar ();

    while (!isdigit(ch)) { if (ch == '-') f = -1 ;ch = getchar();}

    while (isdigit(ch)) res = (res << 1) + (res << 3) + (ch ^ 48) ,ch = getchar(); return res * f ;

}

const int Maxn = 1<<20 ;

int n , m ;

int x[Maxn];

int y[Maxn];

int f[Maxn];

int cnt = 0 ;

int top = 0 ;

double ans = 0.0 ;

struct P{ int x,y; double val;};

P a[Maxn] ;

inline bool cmp_(P a,P b) {

    if(a.val==b.val) return a.x<b.x;

    return a.val<b.val;

}

inline int find ( int x ) { return x == f[x] ? f[x] : f[x] = find(f[x]) ; }

inline void merge( int x , int  y) {

    f[ find(x) ] = find (y) ;

}

inline void kruskal() {

    int count = 0 ;

    sort(a+1,a+cnt+1,cmp_) ;

    for(register int i=1;i<=cnt;i++) {

        count ++ ;

        if(find(a[count].x) != find(a[count].y)) ans += a[i].val , merge(a[i].x,a[i].y) ;

        //if(count == n-1) break ;

    }

    return ;

}

signed main () {

    n=read(); m=read();

    for(register int i=1;i<=n;i++) {

        x[i]=read(),y[i]=read();

    }

    for(register int i=1;i<=n;i++) {

        f[i]=i;

    }

    for(register int i=1; i<=n; i++)

        for(register int j=i+1; j<=n; j++) {

        	cnt ++ ;

            a[cnt].x=i; a[cnt].y=j;

            a[cnt].val=sqrt(pow((x[i]-x[j]),2)+pow((y[i]-y[j]),2));

        }

    for(register int i=1;i<=m;i++) {

        int A=read(),B=read();

        cnt ++ ;

        a[cnt].x = A ; a[cnt].y = B ; a[cnt].val = 0.0 ;

    }

    kruskal() ;

    printf("%.2lf\n",ans) ;

    return 0;

}

随机推荐

函数式中的 currying
currying 是函数式语言中经常遇到的一个概念,翻译成柯里化,不是库里化. currying 指的是将接收多个参数的函数变换成接收一个单一参数,并且返回接收余下的参数而且返回结果的新函数的技术. ...
Flexbox，更优雅的布局
在设计的眼中,排版的操作是一件很简单的事情,靠左.置中.靠右,我只要点一下,所有元素,就会乖乖的到指定的位置. 但到了前端在排版的实现上,就不是这样了. 我们常常得用一堆其实本来不是这样用的属性来做 ...
R-数据导入
目录键盘输入导入文本文件导入Excel文件访问数据库管理系统键盘输入 > mydata <- data.frame(age=numeric(0), gender=characte ...
webstorm常用快捷键（常用）
ctrl+/ 注释 ctrl+shift+/ 注释一块的代码 ctrl+shift+z 返回撤撤销前的操作 ctrl+shift+up/down 代码向上/向下移动 ctrl+b或ctrl+鼠标左键单 ...
递推DP URAL 1353 Milliard Vasya&&num;39&semi;s Function
题目传送门 /* 题意:1~1e9的数字里,各个位数数字相加和为s的个数递推DP:dp[i][j] 表示i位数字,当前数字和为j的个数状态转移方程:dp[i][j] += dp[i-1][j-k] ...
mysql备份和恢复
摘自:http://safe.it168.com/a2009/1108/805/000000805490.shtml 要备份数据库" phpbb_db_backup " #mysq ...
ASP&period;NET-FineUI开发实践-10
嵌套Grid,光棍月大放送,不藏着掖着.实在写的不好,没脸藏啊~只考虑显示排序修改什么的都不管! 话说三石官网加实例了,http://fineui.com/demo/#/demo/grid/grid_ ...
在Centos环境下安装兼容Apache2&period;4高版本SVN服务
在阿里云Centos环境下,搭建PHP运行环境,PHP选择了php7版本,Mysql选择了5.7版本,Apache选择了2.4版本,在搭建SVN版本控制服务过程中出现了不兼容问题,当前环境下Apach ...
1&period;1 java语言有什么优点
1.java是一种纯面向对象的语言.(更易理解和学习) 2.平台无关性.(java是一种解释性的语言,编译器会把java语言变成中间代码,然后在JVM上运行,可移植性) 3.java提供了很多内置的库 ...
HDFS原理
1 ． NameNode 概述 a. NameNode 是 HDFS 的核心. b. NameNode 也称为 Master. c. NameNode 仅存储 HDFS 的元数据:文件系统中所有文件的 ...

秒客网

$P2872\ [USACO07DEC]道路建设Building\ Roads$

随机推荐

相关文章