题解：P14362 [CSP-S 2025] 道路修复 / road（民间数据）

· · 题解

[CSP-S 2025] 道路修复 / road

过民间数据了来水一发。

发现 k 非常小，因此考虑枚举哪些村庄被操作。

使图联通且花费最小，这符合最小生成树的定义。因此考虑建边后跑 Kruskal，时间复杂度 O(2^k(m+nk)\log (m+nk))。

这并不能接受，于是考虑缩小边集大小。先说结论：加入一个或多个与所有点都有连边的新点，原图的任意最小生成树与新边集组成图的最小生成树，同时也是新图的最小生成树。

证明：若原图最小生成树上的一条边不再是树边，则一定是有若干条边权更小的边使其两侧联通。当枚举到比该条边边权更大的边时，原图满足的联通关系此时也一定满足，原本无法加的边此时也一定还是加不了，因此是新图最小生成树。

由此，先求出原图的最小生成树边集，之后再做同样的操作即可。时间复杂度 O(m\log m+2^k(n+nk)\log (n+nk))。

任然不够优。可以使用技术排序优化掉 \log，或者在外面排序，里面直接扫或者归并优化掉 \log。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 20 , M = 1e6 + 5;
int n , m , k;
struct edge
{
    int u , v , w;
    bool operator < (edge E) const
    {return w < E.w;}
} a[M] , b[M];
int C[11];
int f[N];
int find (int u)
{
    if (f[u] == u) return u;
    return f[u] = find (f[u]);
}
vector <edge> g;
signed main ()
{
    ios::sync_with_stdio (0);
    cin.tie (0) , cout.tie (0);
    cin >> n >> m >> k;
    for (int i = 1;i <= m;i ++)
    {
        cin >> a[i].u >> a[i].v >> a[i].w;
    }
    int cc = 0;
    for (int i = 0;i < k;i ++)
    {
        cin >> C[i];
        for (int j = 1;j <= n;j ++)
        {
            int x;
            cin >> x;
            b[++ cc] = {i , j , x};
        } 
    }
    sort (a + 1 , a + m + 1);
    sort (b + 1 , b + cc + 1);
    for (int i = 1;i <= n;i ++) f[i] = i;
    int ans = 0;
    for (int i = 1;i <= m;i ++)
    {
        int u = find (a[i].u) , v = find (a[i].v);
        if (u != v) f[u] = v , g.push_back (a[i]) , ans += a[i].w;
    }
    int A = 1 << k;
    for (int S = 1;S < A;S ++)
    {
        int p = 1 , sum = 0;
        for (int i = 1;i <= n + k;i ++) f[i] = i;
        for (int i = 0;i < k;i ++) if (S >> i & 1) sum += C[i];
        for (auto [u , v , w] : g)
        {
            while (p <= cc && b[p].w <= w)
            {
                if (S >> b[p].u & 1)
                {
                    int fu = find (b[p].u + n + 1) , fv = find (b[p].v);
                    if (fu != fv) f[fu] = fv , sum += b[p].w;
                }
                p ++;
            }
            int fu = find (u) , fv = find (v);
            if (fu != fv) f[fu] = fv , sum += w;
            if (sum >= ans) break;
        }
        ans = min (ans , sum);
    }
    cout << ans;
    return 0;
}