• CCF-CSP真题《202305-4 电力网络》思路+python，c++满分题解

     想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全

    试题编号：202305-4
    试题名称：电力网络
    时间限制：1.0s
    内存限制：512.0MB
    问题描述：

    问题描述

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

    输入格式

    从标准输入读入数据。

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

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

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

    输出格式

    输出到标准输出中。

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

    样例输入

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

    Data

    样例输出

    5

    Data

    样例说明

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

    子任务

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

    对于 20% 的数据，保证 N≤6，K≤10。

    对于另外 20% 的数据，保证 N≤104，K≤10，M=N−1。

    对于另外 20% 的数据，保证 N≤104，K≤10，M=N。

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

    对于最后 20% 的数据，保证 N≤104，K≤10，且度数大于 2 的节点数量 ≤6。

    真题来源：电力网络

    感兴趣的同学可以如此编码进去进行练习提交

    c++ 80分题解： 

    1. #include 
    2. using namespace std;
    3. using LL = long long;
    4.  
    5. const LL inf = 1e18;
    6.  
    7. int main(){
    8.     ios::sync_with_stdio(false);
    9.     cin.tie(0);cout.tie(0);
    10.     int n, k, m;
    11.     cin >> n >> m >> k;
    12.     vectorint>> pcost(n, vector<int>(k));
    13.     for(auto &i : pcost)
    14.         for(auto &j : i)
    15.             cin >> j;
    16.     vectorint, 2>>> edge(n);
    17.     vectorint, 2>> edges(m);
    18.     vectorint>> ecost(m, vector<int>(k * k));
    19.     for(int i = 0; i < m; ++ i){
    20.         int u, v;
    21.         cin >> u >> v;
    22.         edges[i] = {u, v};
    23.         edge[u].push_back({v, i});
    24.         edge[v].push_back({u, i});
    25.         for(auto &j : ecost[i])
    26.             cin >> j;
    27.     }
    28.     if (n <= 6 && k <= 10){
    29.         vector<int> used(n);
    30.         LL ans = inf;
    31.         LL tmp = 0;
    32.         function<void(int)> dfs = [&](int x){
    33.             if (x == n){
    34.                 LL back = tmp;
    35.                 for(int i = 0; i < m; ++ i){
    36.                     int u = edges[i][0], v = edges[i][1], id = i;
    37.                     int r = used[u] * k + used[v];
    38.                     tmp += ecost[id][r];
    39.                 }
    40.                 ans = min(ans, tmp);
    41.                 tmp = back;
    42.                 return;
    43.             }
    44.             for(int i = 0; i < k; ++ i){
    45.                 tmp += pcost[x][i];
    46.                 used[x] = i;
    47.                 dfs(x + 1);
    48.                 tmp -= pcost[x][i];
    49.             }
    50.         };
    51.         dfs(0);
    52.         cout << ans << '\n';
    53.     }else if (m == n - 1){
    54.         vector> dp(n, vector(k, 0));
    55.         function<void(int, int)> dfs = [&](int u, int fa){
    56.             for(auto e : edge[u]){
    57.                 int v = e[0], id = e[1];
    58.                 if (v == fa)
    59.                     continue;
    60.                 dfs(v, u);
    61.                 for(int i = 0; i < k; ++ i){
    62.                     LL tmp = inf;
    63.                     for(int j = 0; j < k; ++ j){
    64.                         int L = i, R = j;
    65.                         if (u != edges[id][0])
    66.                             swap(L, R);
    67.                         int r = L * k + R;
    68.                         tmp = min(tmp, dp[v][j] + pcost[v][j] + ecost[id][r]);
    69.                     }
    70.                     dp[u][i] += tmp;
    71.                 }
    72.             }
    73.         };
    74.         dfs(0, 0);
    75.         LL ans = inf;
    76.         for(int i = 0; i < k; ++ i)
    77.             ans = min(ans, dp[0][i] + pcost[0][i]);
    78.         cout << ans << '\n';
    79.     }else if (m == n){
    80.         vector<int> id(n);
    81.         iota(id.begin(), id.end(), 0);
    82.         int ignore = 0;
    83.         function<int(int)> findfa = [&](int x){
    84.             return x == id[x] ? x : id[x] = findfa(id[x]);
    85.         };
    86.         for(int i = 0; i < m; ++ i){
    87.             int u = edges[i][0], v = edges[i][1];
    88.             int fu = findfa(u), fv = findfa(v);
    89.             if (fu == fv){
    90.                 ignore = i;
    91.                 break;
    92.             }
    93.             id[fu] = fv;
    94.         }
    95.  
    96.         vector> dp(n, vector(k, 0));
    97.         LL ans = inf;
    98.         int fixed = edges[ignore][0], st = edges[ignore][1];
    99.         for(int col = 0; col < k; ++ col){
    100.             for(auto &i : dp)
    101.                 fill(i.begin(), i.end(), 0);
    102.             function<void(int, int)> dfs = [&](int u, int fa){
    103.                 for(auto e : edge[u]){
    104.                     int v = e[0], id = e[1];
    105.                     if (v == fa || id == ignore)
    106.                         continue;
    107.                     dfs(v, u);
    108.                     for(int i = 0; i < k; ++ i){
    109.                         if (u == fixed && i != col)
    110.                             continue;
    111.                         LL tmp = inf;
    112.                         for(int j = 0; j < k; ++ j){
    113.                             if (v == fixed && j != col)
    114.                                 continue;
    115.                             int L = i, R = j;
    116.                             if (u != edges[id][0])
    117.                                 swap(L, R);
    118.                             int r = L * k + R;
    119.                             tmp = min(tmp, dp[v][j] + pcost[v][j] + ecost[id][r]);
    120.                         }
    121.                         dp[u][i] += tmp;
    122.                     }
    123.                 }
    124.             };
    125.             dfs(st, st);
    126.             for(int i = 0; i < k; ++ i){
    127.                 int L = i, R = col;
    128.                 if (st != edges[ignore][0])
    129.                     swap(L, R);
    130.                 int r = L * k + R;
    131.                 ans = min(ans, dp[st][i] + pcost[st][i] + ecost[ignore][r]);
    132.             }
    133.  
    134.         }
    135.         cout << ans << '\n';
    136.  
    137.     }else{
    138.  
    139.         vector<int> du(n);
    140.         for(int i = 0; i < m; ++ i){
    141.             int u = edges[i][0], v = edges[i][1];
    142.             ++ du[u];
    143.             ++ du[v];
    144.         }
    145.         int target = 0;
    146.         for(int i = 0; i < n; ++ i){
    147.             if (m - du[i] == n - 2){
    148.                 target = i;
    149.                 break;
    150.             }
    151.         }
    152.         vector<int> forbid(n, 0);
    153.         for(auto &e : edge[target]){
    154.             int v = e[0];
    155.             forbid[v] = 1;
    156.         }
    157.         int st = 0;
    158.         while(st == target || forbid[st])
    159.             ++ st;
    160.  
    161.         vector> dp(n, vector(k, 0));
    162.         LL ans = inf;
    163.         for(int col = 0; col < k; ++ col){
    164.             for(auto &i : dp)
    165.                 fill(i.begin(), i.end(), 0);
    166.             function<void(int, int)> dfs = [&](int u, int fa){
    167.                 for(auto e : edge[u]){
    168.                     int v = e[0], id = e[1];
    169.                     if (v == fa)
    170.                         continue;
    171.                     if (v != target)
    172.                         dfs(v, u);
    173.                     for(int i = 0; i < k; ++ i){
    174.                         LL tmp = inf;
    175.                         for(int j = 0; j < k; ++ j){
    176.                             if (v == target && j != col)
    177.                                 continue;
    178.                             int L = i, R = j;
    179.                             if (u != edges[id][0])
    180.                                 swap(L, R);
    181.                             int r = L * k + R;
    182.                             if (v == target){
    183.                                 tmp = min(tmp, 1ll * ecost[id][r]);
    184.                             }else{
    185.                                 tmp = min(tmp, dp[v][j] + pcost[v][j] + ecost[id][r]);
    186.                             }
    187.                         }
    188.                         dp[u][i] += tmp;
    189.                     }
    190.                 }
    191.             };
    192.             dfs(st, st);
    193.             for(int i = 0; i < k; ++ i){
    194.                 ans = min(ans, dp[st][i] + pcost[st][i] + pcost[target][col]);
    195.             }
    196.  
    197.         }
    198.         cout << ans << '\n';
    199.  
    200.     }
    201.  
    202.     return 0;
    203. }

     运行结果：

  • 相关阅读:
    golang http客户端常用API：GET POST HEAD及自定义http客户端代码示例
    python folium 添加地图采样点及距离测量等属性
    IDEA 代码提交前流程及提交日志模板化
    [算法] 第二集 二叉树中的深度搜索
    操作系统——进程与线程の选择题整理
    SpringBoot整合MybatisPlus基本的增删改查，保姆级教程
    设计模式之单例模式
    从0-1 的 swagger
    Spring Boot的自动装配中的@ConditionalOnBean条件装配注解在Spring启动过程中，是如何保证处理顺序靠后的
    摄影后期色彩管理流程（Lightroom篇）
  • 原文地址：https://blog.csdn.net/weixin_53919192/article/details/134233401