布线问题
时间限制:1000 ms | 内存限制:65535 KB
难度:4
1、把所有的楼都供上电。
2、所用电线花费最少
每组测试数据的第一行是两个整数v,e.
v表示学校里楼的总个数(v<=500)
随后的e行里,每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。(哪两栋楼间如果没有指明花费,则表示这两栋楼直接连通需要费用太大或者不可能连通)
随后的1行里,有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 )
(楼的编号从1开始),由于安全问题,只能选择一个楼连接到外界供电设备。
数据保证至少存在一种方案满足要求。
1 4 6 1 2 10 2 3 10 3 1 10 1 4 1 2 4 1 3 4 1 1 3 5 6
4
思路:
最小生成树 Prim 算法 + 并查集。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int INF = 999999999; typedef struct { int a, b, num; } node; node no[505 * 505]; int v, root[505]; bool cmp (node a, node b) { return a.num < b.num; } int Find (int x) { return x == root[x] ? x : root[x] = Find(root[x]); } void init() { for (int i = 1; i <= v; ++i) root[i] = i; } int main() { int n; scanf("%d", &n); while (n--) { int e; scanf("%d%d", &v, &e); init(); for (int i = 0; i < e; ++i) scanf("%d%d%d", &no[i].a, &no[i].b, &no[i].num); sort(no, no + e, cmp); int sum = 0; for (int i = 0; i < e; ++i) { int A = Find(no[i].a); int B = Find(no[i].b); if (A != B) { sum += no[i].num; root[A] = B; } } int Min = INF; for (int i = 0; i < v; ++i) { int ans; scanf("%d", &ans); Min = min(Min, ans); } printf("%d\n", sum + Min); } return 0; }
相关推荐
数据结构课程设计,《网络布线最优方案》,使用GUI编写,位置修改可直接点击相应目标。
针对电子设计自动化中低的通道布线布通率,对影响布通率的因素进行了研究,分析了线网布线次序对通道布线结果的影响,比较了静态排序和动态排序的优缺点,基于最小生成树,提出了一种动态通道布线算法。在布线过程中,根据...
网络综合布线标书++标书+校园网综合布线方案.docx
。。。
。。。
。。。
。。。
课题的目的是设计一个程序,来帮助房主完成装修新房子这项颇为复杂的工程的室内电线的布局,具体内容如下:首先,墙壁上插座的位置是固定的,插座间需要有电线相连,而且要布置得整齐美观,即要求每条线都与至少一条...
C++拉斯维加斯算法结合分枝限界算法解决电路板布线问题.zipC++拉斯维加斯算法结合分枝限界算法解决电路板布线问题.zipC++拉斯维加斯算法结合分枝限界算法解决电路板布线问题.zipC++拉斯维加斯算法结合分枝限界算法...
2022【精品】371页医院智能化系统+综合布线+建筑节能方案+弱电消防动力机房监控综合设计方案-可编辑.pptx
使用Kruskal算法计算最小生成树(最优布线),涉及快速排序算法以及并查集
2022-【精品】140页医院智能化系统+综合布线+建筑节能方案+弱点消防动力机房监控综合设计方案-可编辑.pptx.zip
算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题
印刷电路板最短布线问题 一般解空间树的求解问题 java实现
实验要求:请在下图所给出电路板中,按布线要求,利用队列式或优先队列分支限界法实现从a到b的布线工作
分支限界法 实现布线问题 java中的Swing实现,带有详细的算法说明和图像展示···
这个资料里面是有关电路设计中的一些问题的讲解和需要注意的事项
利用队列解决布线问题的C++代码 利用队列解决布线问题的C++代码