楼间的最小生成树加外界的最小进入就行
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct Tedge
{
int from, to;
int dist;
}Edge, * EEE;
Edge edge[250000];
int count;
int fa[600];
int find(int x)
{
if(x == fa[x])
return x;
fa[x]=find(fa[x]);
return(fa[x]);
}
int cmp(const void *a, const void *b)
{
return (*(EEE)a).dist > (*(EEE)b).dist ? 1 : -1;
}
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
int v, e;
int i;
scanf("%d%d", &v, &e);
for(i=0;i<e;i++)
scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].dist);
count = i;
int min = INT_MAX;
for(i=0;i<v;i++)
{
int a;
scanf("%d", &a);
if(a < min)
min = a;
}
qsort(edge, count, sizeof(edge[0]), cmp);
for(i=0;i<=v;i++)
fa[i] = i;
int num=0, sum=min;
for(i=0;i<count;i++)
{
if(find(edge[i].from) != find(edge[i].to))
{
fa[find(edge[i].from)] = find(edge[i].to);
sum += edge[i].dist;
num++;
if(num == v-1) break;
}
}
printf("%d\n", sum);
}
return 0;
}
分享到:
相关推荐
数据结构课程设计,《网络布线最优方案》,使用GUI编写,位置修改可直接点击相应目标。
针对电子设计自动化中低的通道布线布通率,对影响布通率的因素进行了研究,分析了线网布线次序对通道布线结果的影响,比较了静态排序和动态排序的优缺点,基于最小生成树,提出了一种动态通道布线算法。在布线过程中,根据...
。。。
。。。
。。。
。。。
课题的目的是设计一个程序,来帮助房主完成装修新房子这项颇为复杂的工程的室内电线的布局,具体内容如下:首先,墙壁上插座的位置是固定的,插座间需要有电线相连,而且要布置得整齐美观,即要求每条线都与至少一条...
印刷电路板最短布线问题 一般解空间树的求解问题 java实现
算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题
利用队列解决布线问题的C++代码 利用队列解决布线问题的C++代码
分支限界法 实现布线问题 java中的Swing实现,带有详细的算法说明和图像展示···
实验要求:请在下图所给出电路板中,按布线要求,利用队列式或优先队列分支限界法实现从a到b的布线工作
本文详细介绍了 电路布线问题的详细方法,有详细的源程序代码
费了好大的劲才搞定,应用分支界限法!
用JAVA实现的布线问题求解,用JAVA实现的布线问题求解
本例采用队列式分支限界法解决布线问题,参考:算法设计与分析
算法分析里的布线问题实现,支持100*100范围内的布线问题,可以自己设置布线中的障碍位置。
用分支限界法实现布线问题java代码,分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
通过动态规划的思想解决电路布线问题。 主要分为两个部分:1.求size[i][j]. 2.根据求得的size[i][j]导出最大不相交连线集。
布线问题,和迷宫问题是同一类问题。都是通过广度优先搜索来解决的。当然,深度就更好了。