时间限制:1000 ms | 内存限制:65535 KB
难度:4
描述南阳理工学院要进行用电线路改造,现在校长要求设计师设计出一种布线方式,该布线方式需要满足以下条件:
1、把所有的楼都供上电。
2、所用电线花费最少
输入第一行是一个整数n表示有n组测试数据。(n<5)
每组测试数据的第一行是两个整数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
来源[张云聪]原创上传者张云聪基础题型.....一个字 水代码:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<algorithm>
6 using namespace std;
7 const int maxn=500;
8
9 int father[maxn]; //根
10 int rank[maxn]; //秩
11 int n,v,e;
12
13 struct luo{
14 int from;
15 int to;
16 int val;
17 }str[125000];
18 bool operator < (const luo &a ,const luo &b)
19 {
20 return a.val<b.val; //采用从小到大的顺序排列
21 }
22 void init()
23 {
24 int i;
25 for( i=1; i<=maxn ;i++){
26 father[i]=i;
27 rank[i]=1;
28 }
29 }
30
31 int setfind(int x)
32 {
33 while(x!=father[x])
34 x=father[x];
35 return x;
36 }
37
38 void setunion(int aa,int bb)
39 {
40 if(rank[aa]>rank[bb]){
41 father[bb]=aa;
42 rank[aa]+=rank[bb];
43 }
44 else{
45 father[aa]=bb;
46 rank[bb]+=rank[aa];
47 }
48 }
49
50 int main()
51 {
52 int n,v,e,i;
53 scanf("%d",&n);
54 while(n--)
55 {
56 scanf("%d%d",&v,&e);
57 for(i=0;i<e ;i++)
58 scanf("%d%d%d",&str[i].from,&str[i].to,&str[i].val);
59 sort(str,str+e);
60 int aa,bb,ans;
61 ans=0;
62 init(); //初始化
63 for(i=0;i<e ;i++)
64 {
65 aa=setfind(str[i].from);
66 bb=setfind(str[i].to);
67 if(aa!=bb){
68 ans+=str[i].val;
69 setunion(aa,bb);
70 }
71 }
72 int minc=0x3f3f3f3f,tem;
73 for(i=0;i<v;i++)
74 {
75 scanf("%d",&tem);
76 if(tem<minc)minc=tem;
77 }
78 printf("%d\n",ans+minc);
79 }
80 return 0;
81 }