首页 > 其他分享 >déce. 21 修路

déce. 21 修路

时间:2022-12-21 17:25:29浏览次数:85  
标签:ch 21 修路 int ce second edge long first

https://www.luogu.com.cn/problem/P2872

数据范围不大,所以可以暴力处理图,然后用最小生成树
已经加进去的边不可能再加一次了,并查集会自动把他们筛掉

调试的时候一直不出答案,很离谱
最终发现是因为没有输入n和m。。。。。
然后数组开小了,改对了就没问题了

#include<bits/stdc++.h>
using namespace std;
#define in Read()
typedef long long ll;
#define int long long

int in{
    int i=0,f=1; char ch=0;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=1e3+5;
int n,m,tot,fa[N],cnt;
double ans;
pair<int,int> d[N];
struct edge{
    int u,v;
    double w;
    edge(){}
    edge(int U,int V,double W){u=U, v=V, w=W;}
}e[N*N];

double dis(int u,int v){ return sqrt((d[u].first-d[v].first)*(d[u].first-d[v].first)+(d[u].second-d[v].second)*(d[u].second-d[v].second));}
bool cmp(const edge &a, const edge &b){ return a.w<b.w;}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}

signed main(){

    // freopen("1.in","r",stdin);

    n=in,m=in;

    for(int i=1;i<=n;++i){
        int x=in,y=in;
        d[i]=make_pair(x,y);
    }

    for(int i=1;i<=n;++i) fa[i]=i;

    for(int i=1;i<=m;++i){
        int u=get(in), v=get(in);
        if(u==v) continue;
        ++tot;
        fa[u]=v;
    }

    for(int u=1;u<=n;++u)
        for(int v=u+1;v<=n;++v)
            e[++cnt]=edge(u,v,dis(u,v));

    // for(int i=1;i<=cnt;++i) printf("%d %d %.2lf\n",e[i].u,e[i].v,e[i].w);
    
    sort(e+1,e+cnt+1,cmp);
    
    for(int i=1;i<=cnt;++i){
        int u=get(e[i].u),v=get(e[i].v);
        if(u==v) continue;
        ++tot;
        fa[u]=v;
        ans+=e[i].w;
        if(tot==n-1){
            printf("%.2lf\n",ans);
            return 0;
        }
    }
    
}

标签:ch,21,修路,int,ce,second,edge,long,first
From: https://www.cnblogs.com/antimony-51/p/16996668.html

相关文章

  • [bug] org.apache.poi,row.cellIterator() 得到的单元格顺序不正确
    使用的Excel导入工具使用了poi的row.cellIterator()方法,返回的数据List没有按照原来表格的列顺序排列。我使用的版本是4.1.2。到官网查看了changelog,这个bug似乎到今天也......
  • 存量时代下 用低代码开发平台提升你的CEM
    随着人口及流量红利的逐步见顶,我国经济从增量市场迈入存量市场。在充分竞争的存量市场环境下,传统的初级竞争模式无法支撑产业的发展,相反还会让企业陷入持续烧钱的恶性循环......
  • Media Encoder 2021 for Mac(ame 2021永久版) v15.4.1中文版
    MediaEncoder2021中文版是一款优秀的视频音频编码器,能够将多种设备格式的音频或视频进行导出,提供了丰富的硬件设备编码格式设置以及专业设计的预设设置,方便用户导出与特定......
  • [Codeforces Round #836 (Div. 2)C
    C这一次呢,题目要求让a[1]=x,a[n]=1,我们需要找到一个最小的序列使得每一个a[i]都可以被它的下标整除,没找到就是输出-1我第一次是想着先让a[1]=x,a[n]=1,然后在中间一个一......
  • openpyxl.utils.exceptions.IllegalCharacterError报错原因及解决办法
    openpyxl.utils.exceptions.IllegalCharacterError原因Excel表中有非法字符,这些字符都是八进制的,需要进行清洗解决办法一:(自己亲测有效)importredefdata_cl......
  • 存量时代下 用低代码开发平台提升你的CEM
    随着人口及流量红利的逐步见顶,我国经济从增量市场迈入存量市场。在充分竞争的存量市场环境下,传统的初级竞争模式无法支撑产业的发展,相反还会让企业陷入持续烧钱的恶性循环中......
  • Centos中文字体乱码
    安装字体安装字体程序yum-yinstallcups-libsfontconfigttmkfdir创建中文字体目录mkdir/usr/share/fonts/chinesechmod-R755/usr/share/fonts/chinese......
  • CentOS 7.9 安装 containerd(转载)
    containerd安装及使用containerd安装安装containerdyuminstall-yyum-utilsyum-config-manager--add-repohttps://download.docker.com/linux/centos/docker-ce......
  • HTML-2022-12-21
    HTMLhypertextmarkuplanguage 超文本(图片,文本,音频,视频,动画等)标记语言网页-右键-审查元素即可看到网页代码世界知名浏览器都支持HTML5W3C标准 WORLDWIDE......
  • 工业SCADA平台eForceCon是什么,工业SCADA平台eForceCon产品特点
    上海力控元申工业SCADA平台组态软件eForceCon应用于中大型SCADA调度系统,是助力智能工厂建设的统一监控平台。其设计涵盖从现场监控站到调度中心,为企业提供从下到上的完整的......