发帖
雷达卡
C 国的交通网络由 n 座城市和 m 条双向道路构成，每条道路连接两座城市。第 i 条道路（1 ≤ i ≤ m）连接城市 ui 与 vi。整个交通系统是连通的，任意两个城市之间都可以通过若干道路相互抵达。
然而，一场大地震导致所有 m 条道路全部损毁。修复第 i 条道路需要花费 wi 的费用。此外，C 国还有 k 个待进行城市化改造的乡镇。对第 j 个乡镇（1 ≤ j ≤ k）实施城市化改造需支出 cj 的成本。一旦完成改造，便可从该乡镇向原有的 n 座城市分别修建新道路。其中，从第 j 个乡镇到第 i 座城市（1 ≤ i ≤ n）修建一条道路的成本为 aj,i。
政府可以选择任意数量的乡镇进行城市化改造，也可以一个都不选。目标是以最低总成本确保原有的 n 座城市之间实现两两连通——即任意两座原城市可以通过修复或新建的道路路径互相到达。
你的任务是计算出达成这一目标所需的最小总费用。
输入格式
第一行包含三个非负整数 n、m 和 k，分别表示原始城市的数量、道路总数以及可进行城市化改造的乡镇数目。
接下来的 m 行中，第 i 行（1 ≤ i ≤ m）给出三个非负整数 ui、vi、wi，描述第 i 条道路所连接的城市及其修复开销。
随后的 k 行中，第 j 行（1 ≤ j ≤ k）包含 n + 1 个非负整数：cj 后跟 aj,1, aj,2, ..., aj,n，依次表示对第 j 个乡镇进行城市化改造的费用，以及从该乡镇通往各原始城市的道路建设费用。
输出格式
输出一行，包含一个非负整数，代表使原有 n 座城市完全连通的最低总成本。
样例输入 #1
4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4样例输出 #1
13样例解释
一种可行方案为：修复第 3 条和第 4 条道路，并对第 1 个乡镇实施城市化改造，随后在其与第 1 和第 3 号城市之间新建道路。总费用为 5 + 4 + 1 + 1 + 2 = 13。可以证明，不存在低于 13 的方案能够实现四座原始城市的全连通。
其他样例说明
样例 2 对应文件目录下的 road/road2.in 与 road/road2.ans，符合测试点 11 和 12 的限制条件。
样例 3 对应文件目录下的 road/road3.in 与 road/road3.ans，适用于测试点 13 和 14 的情况。
样例 4 对应文件目录下的 road/road4.in 与 road/road4.ans，满足测试点 15 和 16 的数据约束。
数据范围
对于所有测试用例：
- 1 ≤ n ≤ 10
- 1 ≤ m ≤ 10
- 0 ≤ k ≤ 10
- 对于所有 1 ≤ i ≤ m，有 1 ≤ ui, vi ≤ n，ui ≠ vi，且 0 ≤ wi ≤ 10
- 对于所有 1 ≤ j ≤ k，有 0 ≤ cj ≤ 10
- 对于所有 1 ≤ j ≤ k 和 1 ≤ i ≤ n，有 0 ≤ aj,i ≤ 10
对于满足条件的整数范围：1 ≤ i ≤ n 且 1 ≤ j ≤ k，均有 0 ≤ aj,i ≤ 109；同时，任意两座原始城市之间都可以通过若干条已有的道路相互连通。
::cute-table{tuack}| 测试点编号 | n ≤ | m ≤ | k ≤ | 特殊性质 |
|---|---|---|---|---|
| 1～4 | 104 | 106 | 0 | 无 |
| 5, 6 | 103 | 105 | 5 | A |
| 7, 8 | ^ | ^ | ^ | 无 |
| 9, 10 | ^ | 106 | ^ | A |
| 11, 12 | ^ | ^ | ^ | 无 |
| 13, 14 | ^ | ^ | 10 | A |
| 15, 16 | ^ | ^ | ^ | 无 |
| 17, 18 | 104 | ^ | 5 | A |
| 19, 20 | ^ | ^ | ^ | 无 |
| 21～25 | ^ | ^ | 10 | ^ |
特殊性质 A 的定义如下：对所有 1 ≤ j ≤ k，均有 cj = 0，并且存在至少一个 1 ≤ i ≤ n，使得 aj,i = 0 成立。
题解思路
根据题目描述，可以初步设计出一种暴力解法，能够获得 64 分。具体做法是枚举每个乡村是否被选中的 2k 种状态，在每种状态下构建对应的图并运行最小生成树（MST）算法。该方法的时间复杂度为 O(2k(m + nk) log(m + nk))。
进一步观察 MST 的一个关键性质：若某条边在原图的 MST 中未被选用，则在向图中添加新边后，这条边也不会出现在新的 MST 中。基于这一性质，我们可以先对原始城市的道路网络单独运行一次 MST 算法，从而将原图的边数压缩至 O(n) 级别。
在此基础上再进行乡村加入状态的枚举，此时每次 MST 计算的规模显著减小。优化后的总时间复杂度约为 O(2knk log nk log n)，若提前对边排序，则可进一步降低为 O(2knk log n)，此版本可得 80 分。
为了达到满分，需引入两个关键剪枝策略：
- 将城市的权重标记为 1，乡村标记为 0；当某个连通块内权重总和等于 n 时，说明所有城市已被连接，即可提前终止计算。
- 加入最优性剪枝，并将并查集中的递归查找改为迭代实现，以提升效率并避免深层递归带来的开销。
经过上述优化后，算法能够在规定时间内通过全部测试点，获得 100 分。
参考代码结构说明
代码采用 C++ 实现，核心部分包括边结构体定义、并查集操作、Kruskal 算法封装以及主状态枚举逻辑。使用了高效的输入处理和容器管理方式，确保在大规模数据下仍具备良好性能。
4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4主要变量说明：
- e[N], b[N]：存储原始边与扩展边；
- head[N], nxt[N]：链式前向星存图结构；
- f[N]：并查集父节点数组；
- sss[N]：记录各连通块所包含的城市数量；
- c[k], a[k][N]：分别表示乡村建设代价及连接信息；
- mp：用于映射节点编号；
- ss：保存参与 MST 构建的有效边索引集合。
函数功能简述：
- add()：向邻接表中插入一条边；
- find()：带路径压缩的并查集查找函数；
- kruskal(int x)：根据当前乡村选择状态 x 执行 MST 构造；
- read()：快速读入整数。
13while(ch < 48 || ch > 57) ch = getchar();
while(48 <= ch && ch <= 57)
{
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar();
}
return x;
}
int main()
{
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
n = read(), m = read(), k = read();
for(int i = 1; i <= m; ++i)
e[i].u = read(), e[i].v = read(), e[i].w = read(), e[i].id = -1;
vector<int> av;
for(int i = 1; i <= m; ++i)
av.pb(e[i].w);
int tmp = 0;
for(int i = 0; i < k; ++i)
{
c[i] = read();
tmp = max(tmp, c[i]);
for(int j = 1; j <= n; ++j)
av.pb(a[i][j]);
}
sort(av.begin(), av.end());
av.erase(unique(av.begin(), av.end()), av.end());
int tot = 0;
for(int val : av)
mp[val] = ++tot;
for(int i = 1; i <= n; ++i)
f[i] = i;
sort(e + 1, e + 1 + m);
for(int i = 1; i <= m; ++i)
{
int fu = find(e[i].u), fv = find(e[i].v);
if(fu == fv) continue;
int pos = mp[e[i].w];
add(pos, e[i]);
ss.pb(pos);
f[fu] = fv;
}
for(int i = 0; i < k; ++i)
{
for(int j = 1; j <= n; ++j)
{
int pos = mp[a[i][j]];
add(pos, (node){n + i + 1, j, a[i][j], i});
ss.pb(pos);
}
}
sort(ss.begin(), ss.end());
ss.erase(unique(ss.begin(), ss.end()), ss.end());
if(!tmp)
{
cout << kruskal((1 << k) - 1);
return 0;
}
ll ans = 1e18;
for(int i = 0; i < (1 << k); ++i)
ans = min(ans, kruskal(i));
cout << ans;
return 0;
}
黄浦区
京公网安备 11010802022788号
