# 最小生成树

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

Acwing1146 新的开始

原题链接:Acwing1146

题目大意:发展采矿业当然首先得有矿井,小 F 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井,但他似乎忘记了考虑矿井供电问题。

为了保证电力的供应,小 F 想到了两种办法:

  1. 在矿井 i 上建立一个发电站,费用为$ v_i$(发电站的输出功率可以供给任意多个矿井)。
  2. 将这口矿井 i 与另外的已经有电力供应的矿井 j 之间建立电网,费用为 $p_{ij}$。

小 F 希望你帮他想出一个保证所有矿井电力供应的最小花费方案。

……

READ MORE

Acwing1144 连接格点

原题链接:Acwing1144

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

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

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

……

READ MORE

Recents
Categories
Tags
Links