C++城市公交网建设问题
2021/8/25 14:06:14
本文主要是介绍C++城市公交网建设问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少?
输入格式
n(城市数,1≤n≤100)
e(边数)
以下e行,每行3个数 i , j , w[i][j],表示在城市 (i,j) 之间修建高速公路的造价。
输出格式
n-1行,每行为两个城市的序号(a,b)(a<=b),表明这两个城市间建一条高速公路。
输出顺序如下:
输出每条边时按照 a < b 的格式输出,优先按照a从小到大排列,若a相等,则按照b从小到大排列
样例
样例输入
5 8 1 2 2 2 5 9 5 4 7 4 1 10 1 3 12 4 3 6 5 3 3 2 3 8
样例输出
1 2 2 3 3 4 3 5
数据范围与提示
1≤n≤100
w[i][j]≤50
这是一道最小生成树的板子题,根据 n,可得 m ≤ 4950,所以 Kruscal 算法是可行的,时间复杂度为O(mlogm)。
输出:先用结构体把答案存储下来,然后按题目要求排序,Orz!
AC Code:
#include <bits/stdc++.h> using namespace std; const int maxn = 105; int father[maxn], n, m, u, v, w, tot; struct edge { int x, y, z; bool operator<(const edge &a) const { return z < a.z; } }; struct node { int a, b; bool operator<(const node &t) const { return (a < t.a) || (a == t.a && b < t.b); } } f[maxn]; vector<edge> G; void makeSet(int n) { for (int i = 1; i <= n; i++) father[i] = i; } int findSet(int x) { if (father[x] == x) return x; return father[x] = findSet(father[x]); } void Kruskal() { makeSet(n); sort(G.begin(), G.end()); int edgeNum = 0; for (int i = 0; i < m; i++) { int x = findSet(G[i].x), y = findSet(G[i].y); if (x != y) { father[x] = y; f[tot].a = min(G[i].x, G[i].y), f[tot++].b = max(G[i].x, G[i].y); edgeNum++; } if (edgeNum == n - 1) return; } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &u, &v, &w); G.push_back(edge({ u, v, w })); } Kruskal(); sort(f, f + tot); for (int i = 0; i < tot; i++) printf("%d %d\n", f[i].a, f[i].b); return 0; }
这篇关于C++城市公交网建设问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享