标签 - Kruscal

? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 线段树 ? ? Kruscal ?    2018-09-25 08:06:17    338    0    0
Description在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建m条双向道路,其中修建第i条道路的费用为ci。B yteasar作为Byteland公路建设项目的总工程师,他决定选定一个区间[l,r],仅使用编号在该区间内的道路。他希 望选择一些道路去修建,使得连通块的个数尽量少,同时,他不喜欢修建多余的道路,因此每个连通块都可以看成 一棵树的结构。为了选出最佳的区间, Byteasar会不断选择 q个区间,请写一个程序,帮助 Byteasar计算每个区 间内修建公路的最小总费用。  Input第一行包含三个正整数n; m; q,表示城市数、道路数和询问数
? 解题记录 ? ? BZOJ ? ? cdq分治 ? ? 分治 ? ? Kruscal ?    2018-05-21 18:44:15    480    0    0
【题目描述】PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。 【输入】文件第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。 接下来M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi
? 解题记录 ? ? 洛谷 ? ? LCT ? ? Kruscal ?    2018-04-04 15:01:00    629    0    0
题目描述为了得到书法大家的真传,小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图,节点标号为 1,2,3,…,n,边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点,隐士则住在 n 号节点。小 E 需要通过这一片魔法森林,才能够拜访到隐士。 魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪 就会对其发起攻击。幸运的是,在 1 号节点住着两种守护精灵:A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量,达到自己的目的。 只要小 E 带上足够多的守护精灵,妖怪们就不会发起攻击了。具体来说,无 向图中的
? 解题记录 ? ? Kruscal ? ? 倍增 ? ? BZOJ ?    2017-11-01 07:39:39    309    0    0
1977: [BeiJing2010组队]次小生成树 TreeTime Limit: 10 Sec  Memory Limit: 512 MBSubmit: 3446  Solved: 915[Submit][Status][Discuss]Description小 C 最近学了很多最小生成树的算法,Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时,小 P 又来泼小 C 冷水了。小 P 说,让小 C 求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说: 如果最小生
? 解题记录 ? ? Kruscal ? ? 洛谷 ?    2017-10-19 16:15:36    489    0    0
题目描述国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络; 每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。 任意两个配备了一条卫星电话线路的哨所(两边都ᤕ有卫星电话)均可以通话,无论 他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D,这是受收发器 的功率限制。收发器的功率越高,通话距离 D 会更远,但同时价格也会更贵。 收发器需要统一购买和安装,所以全部哨所只能选择安装一种型号的收发器。换句话 说,每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距 离 D,使得每一对哨所之间至少有一条通话路径(直接的或者
? 解题记录 ? ? HDU ? ? 补档计划第一期 ? ? Kruscal ?    2017-10-01 14:14:44    543    0    0
相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。 Input 输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。 每组数据首先是一个整数C(C <=