首页 > 其他分享 >SP368 CSTREET - Cobbled streets 题解

SP368 CSTREET - Cobbled streets 题解

时间:2024-08-21 20:16:07浏览次数:10  
标签:Cobbled int 题解 边权 streets CSTREET

题意

选 n−1 条道路连接 n 个城市,且使得其修建的价格最小。

分析

最小生成树的模板题,可以用 kruskal 来做。

首先,先将所有的边权从小到大排序。

然后,取当前没有选过的,且边权最小的边,判断它连接的两个点是否同属一个集合,如果不是就把他们加到同一个集合中,再记录答案。

代码很简单,也很容易理解。

struct node{
    int from,to,w;
}e[N*N/2];
void init(){
    for(int i=1;i<=n;i++)f[i]=i;
}
int find(int x){
    if(x==f[x])return x;
    return f[x]=find(f[x]);
}
void un(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx==fy)return ;
    else f[fx]=fy; 
}
bool cmp(node x,node y){
    return x.w<y.w;
}
int kruskal(){
    sort(e+1,e+m+1,cmp);
    int sum=0,cnt=0;//sum权值之和,cnt加入边数
    for(int i=1;i<=m;i++){
        if(find(e[i].from)!=find(e[i].to)){
            un(e[i].from,e[i].to);
            sum+=e[i].w*p;
            cnt++;
            if(cnt==n-1)return sum;
        }
    } 
    return -1;
}

标签:Cobbled,int,题解,边权,streets,CSTREET
From: https://www.cnblogs.com/mengxiaolong/p/18372423

相关文章

  • 莫队的 1.5 近似构造 题解
    前言题目链接:洛谷。感觉T4比T3水,虽然我都没做出来。题意简述给定\(1\simn\)的排列\(a\)和\(m\)个区间\([l_i,r_i]\)。定义值域区间\([L,R]\)的价值为\(\operatorname{val}([L,R])\operatorname{:=}\max\limits_{i=1}^m\sum\limits_{k=l_i}^{r_i}[L......
  • P10892 SDOI2024 题解
    【题意简述】你有一个数字\(n\),每次操作将\(n/2\),如果\(n\)是一个奇数,你会纠结是向上取整还是向下取整。问你最少纠结多少次。多组数据。【思路】为了方便起见,我们在二进制下重新审视这个题目:在二进制下,一个数除以\(2\)等同于右移一位。默认向下取整,因为右移会舍弃......
  • P7706 文文的摄影布置 题解
    P7706文文的摄影布置题解原题读完题,发现是线段树。单点修改+区间查询。不过查询的值有些奇怪,就是了,我们考虑用线段树维护这个ψ值(下称待求值)。对于一个区间的待求值,大概有四种情况:如上图四种情况分别为:待求值最大值在左区间待求值最大值在右区间\(a_i与b_j\)在左......
  • 一元柯西问题解法整理与试证明(傅里叶变换的应用)
    关于柯西问题:  柯西问题是指偏微分方程仅有初始条件而无边界条件的定解问题,常用特征线法、分离变量法、格林函数法以及傅里叶变换求解,柯西问题即对于  其中   为主函数, 为初始条件,求解U(x,t)关于傅里叶变换:公式:对于一维方程f(x)有    或  卷积:若,则......
  • [题解]P2444 [POI2000] 病毒
    P2444[POI2000]病毒题目核心是多模式匹配,所以考虑用对所有模式串建立AC自动机。我们把自动机上,存在一个模式串作为前缀的节点,称作“危险节点”。如果无限长的安全代码存在的话,匹配过程中Trie图上一定有节点会经过多次,即存在环;而且经过的所有节点都不是“危险节点”,否则就包含......
  • TCP通信之经典问题解决
    先看下面的代码,研究下执行后会出现什么?服务端:fromsocketimport*ip_port=('127.0.0.1',8003)buffer_size=1024sock_server=socket(AF_INET,SOCK_STREAM)sock_server.bind(ip_port)sock_server.listen(5)whileTrue:print('服务端建立连接...')conn,addr=soc......
  • P1972 [SDOI2009] HH的项链 题解
    前言这是一篇分块题解,大概的思路洛谷的题解里的巨佬讲的很清楚(我的思路其实和大佬的差不多),可以去看看qaq。因为苯人为了卡常魔改代码,所以在本题解的中间具体步骤展示部分仅展示魔改前的代码(也就是被卡常但是好看一点的代码),魔改后的代码(100pts)在文章最末展示。题意题面传送门......
  • 操作系统基础之磁盘及软考高级试题解析
    概述基本概念磁盘有正反两个盘面,每个盘面有多个同心圆,每个同心圆是一个磁道,每个同心圆又被划分为多个扇区,数据就被存在扇区中。磁头首先寻找到对应磁道,然后等到磁盘进行周期旋转到指定的扇区,才能读取到对应的数据。存取时间=寻道时间+等待时间盘面号(磁头号):0~M-1;由于一......
  • 信号量、PV操作及软考高级试题解析
    信号量在并发系统中,信号量是用于控制公共资源访问权限的变量。信号量用于解决临界区问题,使得多任务环境下,进程能同步运行。此概念是由荷兰计算机科学家Dijkstra在1962年左右提出的。信号量仅仅跟踪还剩多少资源可用,不会跟踪哪些资源是可用的。信号量机制,处理进程同步和互斥的问......
  • 题解:Codeforces Round 967 (Div. 2) B [思维/构造]
    B.GeneratePermutationtimelimitpertest:1.5secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputThereisanintegersequence\(a\)oflength\(n\),whereeachelementisinitially\(-1\).Misukihastwoty......