9169 - 解答题(response)

原题链接

“联系”可看作边。

15pts

暴力枚举每条边/每个模型是否建立,然后判断即可。

复杂度 O(2^{2N+M})

100pts

将原有的点和边称为“原图”。

我们新建两个点,分别为 ST

“建立计算模型”就是指建一条 iS 的边(边权为 X_i)。

“建立图形模型”就是指建一条 iT 的边(边权为 Y_i)。

“建立联系”就是指建一条 A_iB_i 的边(边权为 Z_i)。

在以下四张图上跑最小生成树即可:

  1. 原图。
  2. 加上 SS1 \sim N 的每个节点的边。
  3. 加上 TT1 \sim N 的每个节点的边。
  4. 加上 SS1 \sim N 的每个节点的边,再加上 TT1 \sim N 的每个节点的边。

四种情况在合法的前提下取最小值即可。