JHwong

用户名：dotcpp0724243

访问量：832

签　名：

等　　级
排　　名	3377
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

蓝桥第7/8届练习题解
浏览：89

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

1437: 蓝桥杯历届试题-城市建设

　　作者: JHwong　　　　发表时间：2024-01-15 11:33:27 浏览：34　|　评论：0　

原题链接：蓝桥杯历届试题-城市建设

# 1437: 蓝桥杯历届试题-城市建设

```cpp
/* 
 * 题目 1437: 蓝桥杯历届试题-城市建设
 * 生成树变形 -- 变形点/难点：两个消费维度 + 建设码头代价是点权而非边权 + 生成树算法理解。
 * 第一难点解决方案：拆。不建立码头和建立码头的代价取最小。如果存在包含关系可以只计算一次。但是不存在，建立码头可能单纯只是为了赚钱。
 * 点权 -> 边权：使用O(n^2)扫描建立边权 -> 不可能，数据量过大。
 * 方法2，建立超级源点0，假定0与所有点连接且点权为0。如此点权转置为边权。
 * 算法选择，Prim和Kruscal。按照题意是稀疏图，选Kruscal。
 * debug: 时间超限
 * 合并想的太简单了，优化一下。
 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX_N   100005
#define MAX_M   100005
#define CAN_NOT_BUILD 0
#define SUPER_NODE    0
struct Edge {
  int from, to;
  int cost;

bool operator< (const Edge& other) const {
    return this->cost < other.cost;
  }
  // Edge(int f, int t, int c) : from(f), to(t), cost(c) {};
} e[MAX_N + MAX_M];
int river[MAX_N], quick_set[MAX_N + MAX_M], rank[MAX_N + MAX_M];
int n, m, cnt; // cnt只记录起连接作用的边，即负边不一定被cnt记录。

int Belong(int x) {
  while (x != quick_set[x]) {
    quick_set[x] = quick_set[quick_set[x]];
    x = quick_set[x];
  }
  return x;
}

// 合并集合fx, fy
void union_set(int fx, int fy) {
  if (rank[fx] > rank[fy]) quick_set[fy] = fx;
  else quick_set[fx] = fy;
  if (rank[fx] == rank[fy]) rank[fy] += 1;
}

// m 条边， n个点 生成树, 选用边数cnt
int Kruscal(int m, int n) {
  int res = 0;
  for (int i = 0; i <= n; ++i) quick_set[i] = i; // initialize the quick_set
  std::sort(e, e + m);

for (int i = 0; i < m; i++) {
    int fx = Belong(e[i].from);
    int fy = Belong(e[i].to);
    if (fx != fy || e[i].cost < 0) {//负边铁赚，所以要加入
      res += e[i].cost;
      if (fx != fy) {
        union_set(fx, fy);
        cnt++;
      }
    }
  } // 遍历 m 条边

return res;
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++)
    scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].cost);
  for (int i = 1; i <= n; i++)
    scanf("%d", &river[i]);

int flag = CAN_NOT_BUILD;
  int cost1 = Kruscal(m, n);
  if (cnt == n - 1) flag = !CAN_NOT_BUILD; // 有解

for (int i = 1; i <= n; i++) {
    if (river[i] == -1) continue;
    e[m].from = SUPER_NODE;
    e[m].to = i;
    e[m].cost = river[i];
    m++;
  }
  // 建立码头 -- 题目保证一定有解 -- 第二次可不判断是否有解。
  int cost2 = Kruscal(m, n);
  printf("%d\n", flag ? std::min(cost1, cost2) : cost2);
  return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

矩阵转置（C语言代码）

1437: 蓝桥杯历届试题-城市建设

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言训练-求函数值（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【蟠桃记】（C语言代码）

WU-输出正反三角形（C++代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

关于float，double变量的几点说明

简单的a+b （C语言代码）

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

矩阵转置 （C语言代码）

1437: 蓝桥杯历届试题-城市建设

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言训练-求函数值 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【蟠桃记】 （C语言代码）

WU-输出正反三角形 （C++代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

关于float，double变量的几点说明

简单的a+b （C语言代码）

矩阵转置（C语言代码）

　　评论区

C语言训练-求函数值（C语言代码）

【蟠桃记】（C语言代码）

WU-输出正反三角形（C++代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）