专栏文章

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

zzajasi仍爱着
P14362题解参与者 26已保存评论 43

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
43 条
当前快照
1 份
快照标识符
@minfiewr
此快照首次捕获于
2025/12/02 01:34
3 个月前
此快照最后确认于
2025/12/02 01:34
3 个月前
查看原文

致歉

特别抱歉在刚开始的时候时间复杂度分析有误。很抱歉在这篇题解上浪费太多时间。考虑了一会儿要不要再发出来，感觉那个剪枝对随机数据能优化掉许多，同时也是考场思路的总结，还是发出来吧。

鲜花

原来 nn 是 10410^4，是 1000010000 不是 10001000 啊。
100→52100 \to 52。

考场思路

首先读了 2h 题发现乡村和城市不是一个东西。
注意到 kk 很小，可以暴力枚举每一个买乡村的可能的情况。
注意到答案不可能大于刚开始最小生成树跑出来的值，最后答案用的边也不可能用到刚开始最小生成树以外的边。证明是很显然的。
于是你刚开始跑一遍原图的最小生成树，把边数从 mm 缩成 nn，然后对于每一个状态，暴力加边跑当前的最小生成树，答案取最小值做完了。
复杂度是 Θ(mlog⁡m+2k×(nk+n)log⁡(nk+n))\Theta(m\log m+2^k\times (nk+n)\log (nk+n))。据同学说能把 2k2^k 优化成 k2k^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;
}

评论

共 43 条评论，欢迎与作者交流。

正在加载评论...