CCF-CSP认证考试 202305-4 电力网络 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202305-4 电力网络

时间限制： 1.0s
内存限制： 512.0MB

问题描述

西西艾弗岛电力公司需要修建一套电网对岛上的众多城镇进行供电。电网设施包括建造在城镇中的变电站，与建造在城镇间的输电线路。根据前期的考察结果，电力公司已经确定了哪些城镇之间需要建造输电线路，以使得所有城镇能够被连接成一个电力网络。每座城镇只需要建造一个变电站，却都向电力公司提供了多个建造候选地址。对于每个城镇，不同候选地址的变电站造价不同；对于城镇间的输电线路，其造价也会随着两端变电站的候选地址的变化而变化。因此，电力公司想要知道，在所有候选地址的组合中，电网的总造价（变电站造价加上输电线路造价）最低是多少。

输入格式

从标准输入读入数据。

输入的第一行包括三个正整数 $N$ 、 $M$ 、 $K$ 。表示一共有 $N$ 座城镇，需要建造 $M$ 条输电线路，每座城镇都提供了 $K$ 个变电站候选地址。

接下来输入 $N$ 行，每行表示一个城镇。每行包含 $K$ 个整数，表示该城镇不同候选地址的变电站造价。

接下来 $M$ 行，每行表示一条输电线路，包含 $K^{2}+2$ 个整数。前两个整数表示该输电线路两端的城镇，范围是 $[0,\ N)$ 。第三个整数开始是大小为 $K\times K$ 的矩阵 $T$ 的行主序存储形式。 $T_{ij}$ 表示当输电线路的第一个端点选择候选地址 $i$ ，第二个端点选择候选地址 $j$ 时的线路造价。

输出格式

输出到标准输出中。

输出包含一行，这一行有一个整数，表示电网的最低总造价。

样例输入

2 1 2
1 2
3 4
0 1 1 2 3 4

样例输出

样例说明

城镇 0 与城镇 1 均选择了 0 号地址建造变电站。

子任务

对于全部数据，保证由城镇与输电线路构成的图是无向无重边无自环的连通图，保证单个变电站与单条线路的造价均不超过 1000。

对于 $20\%$ 的数据，保证 $N\le 6$ ， $\le 10$ 。

对于另外 $20\%$ 的数据，保证 $\le 10^4$ ， $\le 10$ ， $M = N - 1$ 。

对于另外 $20\%$ 的数据，保证 $\le 10^4$ ， $\le 10$ ， $M = N$ 。

对于另外 $20\%$ 的数据，保证 $\le 10^4$ ， $\le 10$ 。图中存在两个节点 $S$ 、 $D$ ，保证全图去除 $D$ 节点和与 $D$ 节点相连的边后，可以构成以 $S$ 节点为根的一棵树，而且所有与 $D$ 相连的节点都属于这棵树的叶子节点。

对于最后 $20\%$ 的数据，保证 $\le 10^4$ ， $\le 10$ ，且度数大于 $2$ 的节点数量 $\le 6$ 。

题解

依次把度为 $1$ 和度为 $2$ 的点删除。

记 $w_{i,k}$ 表示第 $i$ 个城镇选择候选地址 $k$ 的变电站造价， $T(u,v)_{i,j}$ 表示输电线路的 $u$ 端点选择候选地址 $i$ ， $v$ 端点选择候选地址 $j$ 时的线路造价。

考虑删除度为 $1$ 的点 $u$ ，它和 $v$ 相连，即存在边 $(u, v)$ 。

可以将 $u$ 的变电站造价和 $(u, v)$ 的线路造价合并到 $v$ 的变电站造价中。

对于 $v$ 的每一个候选地址 $j$ ，遍历 $u$ 的每一个候选地址 $i$ ，选取最小的变电站 $w_{u,i}$ 的造价与线路 $T(u,v)_{i,j}$ 的造价的和，合并到 $w_{v,j}$ 的变电站造价中，即 $w_{v,j}+=\min\limits_{i=0}^{k-1}\{w_{u,i}+T(u,v)_{i,j}\}$ 并将点 $u$ 和与 $u$ 相连的边从图中删去。

删去单个度为 $1$ 的点的时间复杂度为 $\mathcal{O}(k^2)$ 。

考虑删除度为 $2$ 的点 $u$ ，它和 $v_1,v_2$ 相连，即存在边 $u,v_1),(u,v_2)$ 。

可以将 $u$ 的变电站造价和 $u,v_1),(u,v_2)$ 的线路造价合并到 $v_1,v_2)$ 的线路造价中。如果不存在 $v_1,v_2)$ ，直接加一条这样的边即可。

对于 $v_1,v_2$ 的每一组候选地址 $j_1,j_2$ ，遍历 $u$ 的每一个候选地址 $i$ ，选取最小的变电站 $w_{u,i}$ 的造价与线路 $T(u,v_1)_{i,j_1},T(u,v_2)_{i,j_2}$ 的造价的和，合并到 $v_1,v_2)$ 的线路造价中，即 $T(v_1,v_2)_{j_1,j_2}+=\min\limits_{i=0}^{k-1}\{w_{u,i}+T(u,v_1)_{i,j_1}+T(u,v_2)_{i,j_2}\}$ 并将点 $u$ 和与 $u$ 相连的边从图中删去。

删去单个度为 $2$ 的点的时间复杂度为 $\mathcal{O}(k^3)$ 。

如此循环到图中不存在度为 $1, 2$ 的点，由题目所给的数据限制，可以发现剩余的点数不会超过 $6$ 个。

接下来直接暴力，枚举每个点选取的候选地址，计算该选取方案下，电网的最低总造价，取最小值即可。

时间复杂度： $\mathcal{O}(nk^3+\min(6,n)^2k^{\min(6,n)})$ 。

参考代码（234ms，26.52MB）

/*
    Created by Pujx on 2024/3/17.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    //#include ""
#else
    #define dbg(...) void(0)
#endif

const int N = 1e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int w[N][10];
int n, m, t, k, q;
map<int, int> mp[N];
struct edge { int u, v; vector<vector<int>> w; } es[N];
int del[N], in[N];

void work() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            cin >> w[i][j];
    for (int i = 0; i < m; i++) {
        auto& e = es[i];
        cin >> e.u >> e.v;
        e.w.assign(k, vector<int>(k));
        for (auto& v : e.w)
            for (auto& x : v) cin >> x;
        mp[e.u][e.v] = i;
        mp[e.v][e.u] = i;
        ++in[e.u], ++in[e.v];
    }

    queue<int> q;
    for (int i = 0; i < n; i++) if (in[i] <= 2) q.push(i);
    while (!q.empty()) {
        auto transposi = [&] (auto& e) {
            swap(e.u, e.v);
            for (int i = 0; i < k; i++)
                for (int j = i + 1; j < k; j++)
                    swap(e.w[i][j], e.w[j][i]);
        };
        auto del1 = [&] (int u) {
            assert(mp[u].size() == 1);
            int v = mp[u].begin()->first;
            auto& e = es[mp[u].begin()->second];
            if (u == e.v) transposi(e);
            for (int j = 0; j < k; j++) {
                int mn = inf;
                for (int i = 0; i < k; i++)
                    mn = min(mn, e.w[i][j] + w[u][i]);
                w[v][j] += mn;
            }
            del[u] = 1;
            mp[u].clear();
            mp[v].erase(u);
            if (--in[v] <= 2) q.push(v);
        };
        auto del2 = [&] (int u) {
            assert(mp[u].size() == 2);
            int v1 = mp[u].begin()->first, v2 = mp[u].rbegin()->first;
            auto& e = mp[v1].count(v2) ? es[mp[v1][v2]] : (++in[v1], ++in[v2], es[mp[v1][v2] = mp[v2][v1] = m++] = {v1, v2, vector<vector<int>>(k, vector<int>(k, 0))});
            if (v1 == e.v) swap(v1, v2);
            auto& e1 = es[mp[u][v1]], & e2 = es[mp[u][v2]];
            if (u == e1.v) transposi(e1);
            if (u == e2.v) transposi(e2);
            for (int j = 0; j < k; j++)
                for (int l = 0; l < k; l++) {
                    int mn = inf;
                    for (int i = 0; i < k; i++)
                        mn = min(mn, e1.w[i][j] + e2.w[i][l] + w[u][i]);
                    e.w[j][l] += mn;
                }
            del[u] = 1;
            mp[u].clear();
            mp[v1].erase(u), mp[v2].erase(u);
            if (--in[v1] <= 2) q.push(v1);
            if (--in[v2] <= 2) q.push(v2);
        };

        int u = q.front(); q.pop();
        if (del[u]) continue;
        if (in[u] == 0) break;
        else if (in[u] == 1) del1(u);
        else del2(u);
    }

    vector<int> vv;
    vector<edge> ee;
    for (int i = 0; i < n; i++) if (!del[i]) vv.emplace_back(i);
    for (int i = 0; i < m; i++)
        if (!del[es[i].u] && !del[es[i].v])
            ee.push_back({lower_bound(all(vv), es[i].u) - vv.begin(), lower_bound(all(vv), es[i].v) - vv.begin(), es[i].w});
    int nn = vv.size(), mm = ee.size();
    int ans = inf;
    vector<int> sel(nn);
    function<void(int, int)> dfs = [&] (int i, int sum) {
        if (i == nn) {
            int tem = sum;
            for (int j = 0; j < mm; j++)
                tem += ee[j].w[sel[ee[j].u]][sel[ee[j].v]];
            ans = min(ans, tem);
            return;
        }
        for (int j = 0; j < k; j++) {
            sel[i] = j;
            dfs(i + 1, sum + w[vv[i]][j]);
        }
    };
    dfs(0, 0);
    cout << ans << endl;
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。

#pragma ... 是用来开启 O2、O3 等优化加快代码速度。

中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。

"" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。

ios::sync_with_stdio(false); (0); (0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。

将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。

秒客网