学校数据结构2022-03-04上机题

T1 冬奥村网络布线方案

问题描述

冬奥会的奥运村是各国运动员在冬奥会期间的住宿公寓，冬奥会期间需要保证奥运村网络畅通，以使运动员都能正常上网。

假定奥运村有 $n$ 个房间，编号为 $0 \cdots n−1$ ，每个房间都需要网络连接。房间 $i$ 有网络，当且仅当满足如下 $2$ 个条件之一：

1. 房间 $i$ 安装了路由器（成本为 $r_i>0$ ）
2. 房间 $i$ 和房间 $j$ 有网线连接且房间 $j$ 有网络（在房间 $i$ 和房间 $j$ 之间布置网线的成本为 $f_{i,j}>0$ ）

假定你是奥组委的网络工程师，请编写程序为奥组委设计一个网络布线方案（哪些房间安装路由器，哪些房间之间布置网线），使得所有房间都有网络，且总成本最小。

点数 $n \le 600$ ，边数不超过 $2 \times 10^5$ 。

题解

可以发现每个点有三种状态，分别是：

1. 第一层：无网络
2. 第二层：有网络（装有路由器）
3. 第三层：有网络（其他房间扩散）

据此，可将每个点分成三层，第一层与原点 $S$ 连权值为零的边（不要网自然不要费用），第一层向第二层对应的点连边，权值为原点权（装路由器通网的费用），第二层向第三层对应点连权值为零的边（本身装路由器了，自然不需要网线），同时，第三层之间的房间可以相互影响，所以依据原图关系，在相应的点之间连边，费用为原边权（装网线费用）。如下图所示。

graph BT

A1((0))
A2((0'))
A3((0''))
B1((1))
B2((1'))
B3((1''))
C1((2))
C2((2'))
C3((2''))
D1((3))
D2((3'))
D3((3''))
E1((4))
E2((4'))
E3((4''))
F1((5))
F2((5'))
F3((5''))
G1((6))
G2((6'))
G3((6''))
S((S))

S---|0|A1
S---|0|B1
S---|0|C1
S---|0|D1
S---|0|E1
S---|0|F1
S---|0|G1
A1---|60|A2
B1---|10|B2
C1---|35|C2
D1---|55|D2
E1---|40|E2
F1---|70|F2
G1---|70|G2
A2---|0|A3
B2---|0|B3
C2---|0|C3
D2---|0|D3
E2---|0|E3
F2---|0|F3
G2---|0|G3
A3---|20|B3
A3---|75|E3
A3---|45|D3
B3---|50|D3
B3---|15|C3
C3---|5|G3
F3---|45|G3
E3---|5|F3
D3---|25|F3
D3---|65|G3

可见，最终的目标就是通过连边覆盖图上的全部节点，只需要进行一遍最小生成树的计算即可。从原点 $S$ 使用 $Prim$ 计算，时间复杂度 $O(n^2)$ 。

T2&T3 冬奥会网站功能提升

问题描述

一个字典里有 $n$ 个字符串及其优先级，之后有 $m$ 个询问，对于每一个询问，给出一个模式串 $p$ ，要求找出优先级前 $K$ 个字符串 $s_1 \cdots s_K$ ，要求 $p$ 是 $s_i,i=1 \cdots K$ 的前缀，且 $p \not= s_i$ 。

题解

对于这个问题，我们并不需要相现实中一样，对于每个询问，立即查找答案，而是先将所有的询问保存下来，再用给出的字符串去往询问中放，看他能成为哪个询问的答案。

这个解法使用了字典树 $Trie$ ，用于处理字符串匹配。

首先将所有询问的字符串放入一个字典树中，同时在节点做上标记，$1$ 代表这是一个字符串的结尾，如样例中形成的字典树如下：

graph TB

A((Root))
B((0))
C((1))
D((1))
E((0))
F((0))
G((1))

A--t-->B
B--h-->C
C--e-->D
A-->|x|E
E-->|x|F
F-->|x|G

之后将所有字典里的字符串按照题目要求，按优先级从高到低排序，将排序后的字符串放到字典树里比较，如果遇到节点为 $1$ ，且节点中存储的答案不超过 $K$ 时，则将字符串作为答案存入该节点。如 $they$ ，比较后则会存入左下方的两个节点。

待所有字典中的字符串都处理完后，再依次用询问的字符串放入字典树比较，匹配成功后，取出末尾节点中的答案输出即可。如 $the$ 则会匹配到最左下方的节点，并输出其中所保存的答案。

设字符串平均长度为 $len$ ，对字典字符串进行排序复杂度 $O(n \log n)$ ，字典树操作复杂度 $O(m \cdot len)$ 。

需要注意的是，在大量的输出数据的情况下，题目 $60ms$ 的时限非常紧促，建议程序中不要使用 $string$ 和其他库函数，最好加上 $inline,register$ 等，整形较小时使用 $short$ 而非 $long\ long$ ，输入输出使用 $gets,fputs$ 等较快的方式。（ $scanf,printf$ 我都过不去）

优化和卡常前后的速度对比：