布线问题
时间限制: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 ",ans+minc); 79 } 80 return 0; 81 }