题解：P14362 [CSP-S 2025] 道路修复 / road（民间数据）
zajasi
·
·
题解
致歉
特别抱歉在刚开始的时候时间复杂度分析有误。很抱歉在这篇题解上浪费太多时间。考虑了一会儿要不要再发出来，感觉那个剪枝对随机数据能优化掉许多，同时也是考场思路的总结，还是发出来吧。
鲜花
原来 n 是 10^4，是 10000 不是 1000 啊。
## 考场思路
首先读了 2h 题发现乡村和城市不是一个东西。
注意到 $k$ 很小，可以暴力枚举每一个买乡村的可能的情况。
注意到答案**不可能**大于刚开始最小生成树跑出来的值，最后答案用的边也**不可能**用到刚开始最小生成树以外的边。证明是很显然的。
于是你刚开始跑一遍原图的最小生成树，把边数从 $m$ 缩成 $n$，然后对于每一个状态，暴力加边跑当前的最小生成树，答案取最小值做完了。
复杂度是 $\Theta(m\log m+2^k\times (nk+n)\log (nk+n))$。据同学说能把 $2^k$ 优化成 $k^2$，不确定是否为真。
为啥要发题解？因为有一行剪枝好像能剪掉许多东西。而且，警钟长鸣。
## code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
int n, m, k;
int x, y, z;
vector<pair<int, pair<int, int>>> vv;
int f[20200];
int F(int x)
{
return f[x] == x ? x : f[x] = F(f[x]);
}
int c[10100];
int a[11][10100];
main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
{
cin >> x >> y >> z;
vv.pb(mp(z, mp(x, y)));
}
for (int i = 1; i <= k; i++)
{
cin >> c[i];
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++)
{
f[i] = i;
}
sort(vv.begin(), vv.end());
int z = 0, zz = 0;
vector<pair<int, pair<int, int>>> v;
for (auto &i : vv)
{
if (F(i.second.first) != F(i.second.second))
{
f[F(i.second.first)] = F(i.second.second);
z += i.first;
zz = i.first;
v.pb(mp(i.first, mp(i.second.first, i.second.second)));
}
}
// cout << z << "\n";
sort(v.begin(), v.end());
for (int i = 0; i < (1 << k); i++)
{
vector<pair<int, pair<int, int>>> g = v;
int re = 0;
for (int j = 1; j <= k; j++)
{
if (i >> (j - 1) & 1)
{
re += c[j];
for (int l = 1; l <= n; l++)
{
if (a[j][l] <= zz)// 就是这里，能筛掉一大部分随机数据。
g.pb(mp(a[j][l], mp(j + n, l)));
}
}
}
for (int j = 1; j <= n + k; j++)
{
f[j] = j;
}
sort(g.begin(), g.end());
for (auto &i : g)
{
if (F(i.second.second) != F(i.second.first))
{
f[F(i.second.second)] = F(i.second.first);
re += i.first;
}
}
z = min(z, re);
}
cout << z;
return 0;
}
```