更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202305-4 电力网络

时间限制： 1.0s 内存限制： 512.0MB

西西艾弗岛电力公司需要修建一套电网对岛上的众多城镇进行供电。电网设施包括建造在城镇中的变电站，与建造在城镇间的输电线路。根据前期的考察结果，电力公司已经确定了哪些城镇之间需要建造输电线路，以使得所有城镇能够被连接成一个电力网络。每座城镇只需要建造一个变电站，却都向电力公司提供了多个建造候选地址。对于每个城镇，不同候选地址的变电站造价不同；对于城镇间的输电线路，其造价也会随着两端变电站的候选地址的变化而变化。因此，电力公司想要知道，在所有候选地址的组合中，电网的总造价（变电站造价加上输电线路造价）最低是多少。

从标准输入读入数据。

输入的第一行包括三个正整数 N N N、 M M M、 K K K。表示一共有 N N N 座城镇，需要建造 M M M 条输电线路，每座城镇都提供了 K K K 个变电站候选地址。

接下来输入 N N N 行，每行表示一个城镇。每行包含 K K K 个整数，表示该城镇不同候选地址的变电站造价。

接下来 M M M 行，每行表示一条输电线路，包含 K 2 + 2 K^{2}+2 K2+2 个整数。前两个整数表示该输电线路两端的城镇，范围是 [ 0 ,   N ) [0,\ N) [0, N)。第三个整数开始是大小为 K × K K\times K K×K 的矩阵 T T T 的行主序存储形式。 T i j T_{ij} Tij​ 表示当输电线路的第一个端点选择候选地址 i i i，第二个端点选择候选地址 j j j 时的线路造价。

输出到标准输出中。

输出包含一行，这一行有一个整数，表示电网的最低总造价。

城镇 0 与城镇 1 均选择了 0 号地址建造变电站。

对于全部数据，保证由城镇与输电线路构成的图是无向无重边无自环的连通图，保证单个变电站与单条线路的造价均不超过 1000。

对于 20 % 20\% 20% 的数据，保证 N ≤ 6 N\le 6 N≤6， K ≤ 10 K \le 10 K≤10。

对于另外 20 % 20\% 20% 的数据，保证 N ≤ 1 0 4 N \le 10^4 N≤104， K ≤ 10 K \le 10 K≤10， M = N − 1 M = N-1 M=N−1。

对于另外 20 % 20\% 20% 的数据，保证 N ≤ 1 0 4 N \le 10^4 N≤104， K ≤ 10 K \le 10 K≤10， M = N M = N M=N。

对于另外 20 % 20\% 20% 的数据，保证 N ≤ 1 0 4 N \le 10^4 N≤104， K ≤ 10 K \le 10 K≤10。图中存在两个节点 S S S、 D D D，保证全图去除 D D D 节点和与 D D D 节点相连的边后，可以构成以 S S S 节点为根的一棵树，而且所有与 D D D 相连的节点都属于这棵树的叶子节点。

对于最后 20 % 20\% 20% 的数据，保证 N ≤ 1 0 4 N \le 10^4 N≤104， K ≤ 10 K \le 10 K≤10，且度数大于 2 2 2 的节点数量 ≤ 6 \le 6 ≤6。

依次把度为 1 1 1 和 度为 2 2 2 的点删除。

记 w i , k w_{i,k} wi,k​ 表示第 i i i 个城镇选择候选地址 k k k 的变电站造价， T ( u , v ) i , j T(u,v)_{i,j} T(u,v)i,j​ 表示输电线路的 u u u 端点选择候选地址 i i i， v v v 端点选择候选地址 j j j 时的线路造价。

考虑删除度为 1 1 1 的点 u u u，它和 v v v 相连，即存在边 ( u , v ) (u,v) (u,v)。

可以将 u u u 的变电站造价和 ( u , v ) (u,v) (u,v) 的线路造价合并到 v v v 的变电站造价中。

对于 v v v 的每一个候选地址 j j j，遍历 u u u 的每一个候选地址 i i i，选取最小的变电站 w u , i w_{u,i} wu,i​ 的造价与线路 T ( u , v ) i , j T(u,v)_{i,j} T(u,v)i,j​ 的造价的和，合并到 w v , j w_{v,j} wv,j​ 的变电站造价中，即 w v , j + = min ⁡ i = 0 k − 1 { w u , i + T ( u , v ) i , j } w_{v,j}+=\min\limits_{i=0}^{k-1}\{w_{u,i}+T(u,v)_{i,j}\} wv,j​+=i=0mink−1​{wu,i​+T(u,v)i,j​} 并将点 u u u 和与 u u u 相连的边从图中删去。

删去单个度为 1 1 1 的点的时间复杂度为 O ( k 2 ) \mathcal{O}(k^2) O(k2)。

考虑删除度为 2 2 2 的点 u u u，它和 v 1 , v 2 v_1,v_2 v1​,v2​ 相连，即存在边 ( u , v 1 ) , ( u , v 2 ) (u,v_1),(u,v_2) (u,v1​),(u,v2​)。

可以将 u u u 的变电站造价和 ( u , v 1 ) , ( u , v 2 ) (u,v_1),(u,v_2) (u,v1​),(u,v2​) 的线路造价合并到 ( v 1 , v 2 ) (v_1,v_2) (v1​,v2​) 的线路造价中。如果不存在 ( v 1 , v 2 ) (v_1,v_2) (v1​,v2​)，直接加一条这样的边即可。

对于 v 1 , v 2 v_1,v_2 v1​,v2​ 的每一组候选地址 j 1 , j 2 j_1,j_2 j1​,j2​，遍历 u u u 的每一个候选地址 i i i，选取最小的变电站 w u , i w_{u,i} wu,i​ 的造价与线路 T ( u , v 1 ) i , j 1 , T ( u , v 2 ) i , j 2 T(u,v_1)_{i,j_1},T(u,v_2)_{i,j_2} T(u,v1​)i,j1​​,T(u,v2​)i,j2​​ 的造价的和，合并到 ( v 1 , v 2 ) (v_1,v_2) (v1​,v2​) 的线路造价中，即 T ( v 1 , v 2 ) j 1 , j 2 + = min ⁡ i = 0 k − 1 { w u , i + T ( u , v 1 ) i , j 1 + T ( u , v 2 ) i , j 2 } T(v_1,v_2)_{j_1,j_2}+=\min\limits_{i=0}^{k-1}\{w_{u,i}+T(u,v_1)_{i,j_1}+T(u,v_2)_{i,j_2}\} T(v1​,v2​)j1​,j2​​+=i=0mink−1​{wu,i​+T(u,v1​)i,j1​​+T(u,v2​)i,j2​​} 并将点 u u u 和与 u u u 相连的边从图中删去。

删去单个度为 2 2 2 的点的时间复杂度为 O ( k 3 ) \mathcal{O}(k^3) O(k3)。

如此循环到图中不存在度为 1 , 2 1,2 1,2 的点，由题目所给的数据限制，可以发现剩余的点数不会超过 6 6 6 个。

接下来直接暴力，枚举每个点选取的候选地址，计算该选取方案下，电网的最低总造价，取最小值即可。

时间复杂度： O ( n k 3 + min ⁡ ( 6 , n ) 2 k min ⁡ ( 6 , n ) ) \mathcal{O}(nk^3+\min(6,n)^2k^{\min(6,n)}) O(nk3+min(6,n)2kmin(6,n))。

关于代码的亿点点说明：