首页 > 试题广场 >

继续畅通工程

[编程题]继续畅通工程
  • 热度指数：11320 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

输入描述:
    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

    当N为0时输入结束。


输出描述:
    每个测试用例的输出占一行，输出全省畅通需要的最低成本。
示例1

输入

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

输出

3
1
0
算法知识视频讲解
开通博客
头像 斩题怪
发表于 2020-04-15 17:36:07
跟前几道畅通工程的题一样，都是用Kruskal算法求最小生成树，唯一的区别是要处理已经修建好的道路 ，我的方法是如果检测到一个道路已经建好，就将他的花费置为0。然后就是常规并查集+Kruskal了 #include <cstdio> #include <io 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 GoodLunatic
发表于 2024-09-02 16:58:10
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int p[N], h[N]; struct Edge { int x, y, v, st; bool o 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客440904392号
发表于 2024-10-02 18:07:51
import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Scanner; public class Main { private static int[] 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 健康快乐最重要
发表于 2020-02-21 20:42:51
几个题基本都是Kruskal算法 #include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; const int maxn=200 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 chong_0428
发表于 2024-03-23 23:02:32
#include <stdio.h> #include <stdlib.h> struct Edge { int from; int to; int cost; int build; }; int father[100]; struct E 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 ChaChaCharis
发表于 2023-03-14 11:27:20
#include <cstdio> #include <iostream> #include <string> #include <algorithm> using namespace std; const int MAX=100; struct 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客32950103号
发表于 2024-03-19 17:13:46
#include "bits/stdc++.h" using namespace std; class Graph{ public: int nodes; vector<list<pair<int,int>>> grap 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 程昱同学
发表于 2023-01-26 11:24:25
#include<bits/stdc++.h> using namespace std; int N, a, b, Cost, state, edge_num; struct edge { int one_pos; int another_pos; int cos 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 chenxuan111
发表于 2024-03-15 14:47:22
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool cmp(vector<int> lhs, vector<int> rh 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Luka_2001
发表于 2024-02-12 22:56:31
#include <iostream> #include<algorithm> using namespace std; #define maxnum 100 int tree[maxnum]; int height[maxnum]; struct edge{ i 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 图 排序 并查集
难度：
69条回答 9367浏览

热门推荐

通过挑战的用户

查看代码

相关试题

继续畅通工程

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号