原题链接
“联系”可看作边。
暴力枚举每条边/每个模型是否建立,然后判断即可。
复杂度 O(2^{2N+M})。
将原有的点和边称为“原图”。
我们新建两个点,分别为 S 和 T。
“建立计算模型”就是指建一条 i 到 S 的边(边权为 X_i)。
“建立图形模型”就是指建一条 i 到 T 的边(边权为 Y_i)。
“建立联系”就是指建一条 A_i 到 B_i 的边(边权为 Z_i)。
在以下四张图上跑最小生成树即可:
四种情况在合法的前提下取最小值即可。