# Kruskal

Acwing356 次小生成树

原题链接:Acwing356

题目描述:给定一张 $N$ 个点 $M$ 条边的无向图,求无向图的严格次小生成树。

设最小生成树的边权之和为 $\rm sum$,严格次小生成树就是指边权之和大于 $\rm sum$ 的生成树中最小的一个。

……

READ MORE

Acwing1148 秘密的牛奶运输

原题链接:Acwing1148

题目描述:农夫约翰要把他的牛奶运输到各个销售点。

运输过程中,可以先把牛奶运输到一些销售点,再由这些销售点分别运输到其他销售点。

运输的总距离越小,运输的成本也就越低。低成本的运输是农夫约翰所希望的。

不过,他并不想让他的竞争对手知道他具体的运输方案,所以他希望采用费用第二小的运输方案而不是最小的。现在请你帮忙找到该运输方案。

……

READ MORE

Acwing346 走廊泼水节

原题链接:Acwing346

题目描述:给定一棵 N 个节点的树,要求增加若干条边,把这棵树扩充为完全图,并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意: 树中的所有边权均为整数,且新加的所有边权也必须为整数。

……

READ MORE

Acwing1145 北极通讯网络

原题链接:Acing1145

题目描述:北极的某区域共有 n 座村庄,每座村庄的坐标用一对整数 (x,y) 表示。

为了加强联系,决定在村庄之间建立通讯网络,使每两座村庄之间都可以直接或间接通讯。

通讯工具可以是无线电收发机,也可以是卫星设备。

无线电收发机有多种不同型号,不同型号的无线电收发机有一个不同的参数 d,两座村庄之间的距离如果不超过 d,就可以用该型号的无线电收发机直接通讯,d 值越大的型号价格越贵。现在要先选择某一种型号的无线电收发机,然后统一给所有村庄配备,数量不限,但型号都是 相同的

配备卫星设备的两座村庄无论相距多远都可以直接通讯,但卫星设备是 有限的,只能给一部分村庄配备。

现在有 k 台卫星设备,请你编一个程序,计算出应该如何分配这 k 台卫星设备,才能使所配备的无线电收发机的 d 值最小。

……

READ MORE

Acwing1144 连接格点

原题链接:Acwing1144

题目大意:有一个 $m$ 行 $n$ 列的点阵,相邻两点可以相连。

一条纵向的连线花费一个单位,一条横向的连线花费两个单位。

某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。

……

READ MORE

Acwing1143 联络员

原题链接:Acwing1143

题目大意:Tyvj已经一岁了,网站也由最初的几个用户增加到了上万个用户,随着Tyvj网站的逐步壮大,管理员的数目也越来越多,现在你身为Tyvj管理层的联络员,希望你找到一些通信渠道,使得管理员两两都可以联络(直接或者是间接都可以)。本题中所涉及的通信渠道都是 双向 的。

Tyvj是一个公益性的网站,没有过多的利润,所以你要尽可能的使费用少才可以。

目前你已经知道,Tyvj的通信渠道分为两大类,一类是必选通信渠道,无论价格多少,你都需要把所有的都选择上;还有一类是选择性的通信渠道,你可以从中挑选一些作为最终管理员联络的通信渠道。

数据保证给出的通信渠道可以让所有的管理员联通。

注意: 对于某两个管理员 $u$, $v$,他们之间可能存在多条通信渠道,你的程序应该累加所有 $u$, $v$ 之间的必选通行渠道。

……

READ MORE

Recents
Categories
Tags
Links