Catshao

用户名：Catshao

访问量：28865

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7135
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1475

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：548

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：556

你可能喜欢

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

继续畅通工程-题解（C++代码）（易懂）

　　作者: Catshao　　　　发表时间：2021-02-12 20:34:26 浏览：176　|　评论：0　

原题链接：继续畅通工程

# Part 1 还是畅通工程

在做这道题之前，我们先来看[这道题](https://www.dotcpp.com/oj/problem1729.html)，下面来贴一下这道题的题解。

--------

这不是prim的算法讲解，prim还没有学会的同学可以去看[这篇prim文章](https://blog.dotcpp.com/a/76409)

## Part 1 读题

看题面，划重点：

>某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但**不一定有直接的公路相连**，只要能间接通过公路可达即可），并要求铺设的公路**总长度为最小**。请计算最小的公路总长度。

由于不需要直接连接，而且总长度最小，不难想出这是一道**最小生成树**的题。本题采用prim算法。

> **测试输入包含若干测试用例。**每个测试用例的第1行给出村庄数目N ( < 100 )；随后的**N(N-1)/2行**对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄**从1到N编号**。
当N为0时，输入结束，该用例不被处理。

由于给出的是距离，所以整张图并不是有向图，而是**无向图**。在输入的时候要注意。

## Part 2 代码

```cpp
//
// Created by Cat-shao on 2021/2/7.
//

#include <cstdio>
#include <deque>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = 1000000000; // 无限的定义，这里也可以改成其他极大值，如INT_MAX
const int MAX_N = 3100;

class edge {
public:
    int to;
    long long cost;
    edge() {
    }

edge(int _to, long long _cost) {
        to = _to;
        cost = _cost;
    }

bool operator < (const edge &e) const { // 重定义小于号，用于将stl的大根堆当小根堆用
        return cost > e.cost;
    }
};

typedef deque<edge> graphType; // 使用邻接表存图

void prim(graphType graph[], long long dis[], int path[], int n, int s)
{
    bool mark[MAX_N]; // mark[i] == false 则节点i没有被访问过
    priority_queue<edge> q; // 队列，用于寻找权值最小的边
    for (int i = 1; i <= n; ++i) { // 初始化为无限
        dis[i] = INF;
    }
    memset(path, 0, sizeof(path));
    memset(mark, 0, sizeof(mark));

dis[s] = 0;
    q.push(edge(s, 0));
    while (!q.empty()) { // 直到队列为空，此时可能为图不连通或遍历完所有的节点
        int index = q.top().to;
        q.pop();
        if (mark[index]) { // 队列中有冗余数据，见之前的文章
            continue;
        }

mark[index] = true; // 标记
        for (graphType::iterator it = graph[index].begin(); it != graph[index].end(); it++) { // 更新周围节点
            if (it->cost < dis[it->to] && !mark[it->to]) {
                dis[it->to] = it->cost;
                path[it->to] = index;
                q.push(edge(it->to, dis[it->to]));
            }
        }
    }
}

int main()
{
    int n, u, v, w;
    long long dis[MAX_N];
    int path[MAX_N];
    while (~scanf("%d", &n) && n != 0) { // 程序会先scanf，再判断n != 0，不会出现循环进不去的现象
        graphType graph[MAX_N];
        for (int i = 0; i < (n * (n - 1) / 2); ++i) {
            scanf("%d%d%d", &u, &v, &w);
            graph[u].push_back(edge(v, w)); // 无向图
            graph[v].push_back(edge(u, w));
        }
        prim(graph, dis, path, n, 1);
        long long sum = 0;
        for (int i = 1; i <= n; ++i) { // 由于prim只给出了dis表，没有给出和，自行相加即可
            sum += dis[i];
        }
        printf("%d\n", sum);
    }
}
```

--------------------

# Part 2 继续畅通工程

通过读题，我们得知**有些路径已经修好**。如何处理这些路径呢？既然这条路已经修好了，那么再修一遍的成本为0（修了个寂寞）。我们只需要在输入的时候判断，**如果这条路修好了，那么就将其权值设置为0**。

- 在prim中，所有的路径都会被遍历到一遍，算法会将权值为0的路径（此题无负边）替换掉已选择的非0路径。
- 在kruskal中，从小到大排序会使权值为0的路径最先被选择。

与上一道题就多出了两行：
```cpp
if (x) { // 修好了
    w = 0; // 白给的路径一定要要
}
```

## 代码

```cpp
//
// Created by Cat-shao on 2021/2/7.
//

#include <cstdio>
#include <deque>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = 1000000000;
const int MAX_N = 3100;

class edge {
public:
    int to;
    long long cost;
    edge() {
    }

edge(int _to, long long _cost) {
        to = _to;
        cost = _cost;
    }

bool operator < (const edge &e) const {
        return cost > e.cost;
    }
};

typedef deque<edge> graphType;

void prim(graphType graph[], long long dis[], int path[], int n, int s)
{
    bool mark[MAX_N];
    priority_queue<edge> q;
    for (int i = 1; i <= n; ++i) {
        dis[i] = INF;
    }
    memset(path, 0, sizeof(path));
    memset(mark, 0, sizeof(mark));

dis[s] = 0;
    q.push(edge(s, 0));
    while (!q.empty()) {
        int index = q.top().to;
        q.pop();
        if (mark[index]) {
            continue;
        }

mark[index] = true;
        for (graphType::iterator it = graph[index].begin(); it != graph[index].end(); it++) {
            if (it->cost < dis[it->to] && !mark[it->to]) {
                dis[it->to] = it->cost;
                path[it->to] = index;
                q.push(edge(it->to, dis[it->to]));
            }
        }
    }
}

int main()
{
    int n, u, v, w, x;
    long long dis[MAX_N];
    int path[MAX_N];
    while (~scanf("%d", &n) && n != 0) {
        graphType graph[MAX_N];
        for (int i = 0; i < (n * (n - 1) / 2); ++i) {
            scanf("%d%d%d%d", &u, &v, &w, &x);
            if (x) {
                w = 0;
            }
            graph[u].push_back(edge(v, w));
            graph[v].push_back(edge(u, w));
        }
        prim(graph, dis, path, n, 1);
        long long sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum += dis[i];
        }
        printf("%d\n", sum);
    }
}
```

0.0分

3 人评分

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

Catshao

TA的其他文章

你可能喜欢

C语言训练-角谷猜想（C语言代码）

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

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

上车人数（C语言代码）

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

继续畅通工程-题解（C++代码）（易懂）

评论区

精彩推荐

哥德巴赫曾猜测（C语言代码）

sizeof的大作用（C语言代码）

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

大家好，我是验题君

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

陶陶摘苹果2 （C语言代码）

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

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

10月月赛题解

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

Catshao

TA的其他文章

你可能喜欢

C语言训练-角谷猜想 （C语言代码）

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

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

上车人数 （C语言代码）

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

继续畅通工程-题解（C++代码）（易懂）

评论区

精彩推荐

哥德巴赫曾猜测 （C语言代码）

sizeof的大作用 （C语言代码）

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

大家好，我是验题君

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

陶陶摘苹果2 （C语言代码）

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

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

10月月赛题解

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

C语言训练-角谷猜想（C语言代码）

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

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

上车人数（C语言代码）

　　评论区

哥德巴赫曾猜测（C语言代码）

sizeof的大作用（C语言代码）