P14362 [CSP-S 2025] 道路修复

题目大意

给定 \(n\) 个点，\(m\) 条边的无向图且有边权，有 \(k\) 个额外点，每个额外点向这 \(n\) 个点连边，且额外点有点权，求最小生成树。
\(n\leq 1e4\)，\(m\leq 1e6\)，\(k\leq 10\)。

Sol

从考场思路改了一点。

先考虑 \(k\leq 0\) 部分分，就是直接跑最小生成树，能获得 \(16\) 分。
特殊性质 A 中，如果点权为 \(0\) 且存在一条边权为 \(0\)，可以直接从边权为 \(0\) 所连点向所有点连边，再跑最小生成树即可。

看看 \(k\) 的范围很小，且比较麻烦的点在于处理它独特的点权，不难想到直接枚举某个点选和不选的子集，这样先把点权代价加上，再将所选额外点的连边加上跑最小生成树就可以了，复杂度 \(O(2^k(m+k)\log (m+k))\)，仍然无法通过这一题。

复杂度瓶颈在于每次枚举子集都要排序，原图的 \(m\) 个边只有 \(n-1\) 个有效，把它们存下来，和 \(nk\) 个额外点连边一起预处理排序，做最小生成树时判断所连点在不在选中范围内就好了。
预处理 \(n-1\) 条边是 \(O(m\log m)\) 的，最后处理复杂度为 \(O((n+nk)\log (n+nk))\)，足以通过本题。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;typedef long long LL;
struct Node {int u , v; LL w;};const int N = 1e4+10 , M = 1e6+10 , K = 15;int n , m , k;
Node tr[M];
vector<Node> vec;
LL ct[K];
int p[N];int find(int x) {if(x != p[x]) p[x] = find(p[x]);return p[x];
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cin >> n >> m >> k;for(int i = 1 ; i <= m ; i ++)cin >> tr[i].u >> tr[i].v >> tr[i].w;for(int i = 1 ; i <= n ; i ++)p[i] = i;sort(tr+1 , tr+m+1 , [](const Node& a , const Node& b) {return a.w < b.w;});int block = n;for(int i = 1 ; i <= m && block > 1 ; i ++) {if(find(tr[i].u) == find(tr[i].v)) continue;vec.emplace_back(tr[i]);p[find(tr[i].u)] = find(tr[i].v);block --;}for(int i = 1 ; i <= k ; i ++) {cin >> ct[i];for(int j = 1 ; j <= n ; j ++) {LL x; cin >> x;vec.push_back({n+i , j , x});}}sort(vec.begin() , vec.end() , [](const Node& a , const Node& b) {return a.w < b.w;});LL res = 0x3f3f3f3f3f3f3f3f;for(int state = 0 ; state < (1<<k) ; state ++) {LL tmpres = 0;for(int j = 0 ; j < k ; j ++) {if(state & (1 << j)) tmpres += ct[j+1];}for(int i = 1 ; i <= n+k ; i ++)p[i] = i;block = n;for(auto i : vec) {if(i.u > n && (state&(1<<(i.u-n-1))) == 0) continue;if(find(i.u) == find(i.v)) continue;tmpres += i.w;p[find(i.u)] = find(i.v);if(i.u <= n) block --;if(block == 1) break;}res = min(res , tmpres);}cout << res << '\n';return 0;
}