布线问题
时间限制：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 <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int map[550][550],vis[550],low[550]; 7 int n; 8 int prim() 9 { 10 int i,j,pos,min,sum=0; 11 memset(low,0,sizeof(low)); 12 memset(vis,0,sizeof(vis)); 13 vis[1]=1;pos=1; 14 for(i=1;i<=n;i++) 15 if(i!=pos) 16 low[i]=map[pos][i]; 17 for(i=1;i<n;i++) 18 { 19 min=200; 20 for(j=1;j<=n;j++) 21 { 22 if(!vis[j]&&low[j]<min) 23 { 24 min=low[j]; 25 pos=j; 26 } 27 } 28 sum+=min; 29 vis[pos]=1; 30 for(j=1;j<=n;j++) 31 { 32 if(vis[j]==0&&low[j]>map[pos][j]) 33 low[j]=map[pos][j]; 34 } 35 } 36 return sum; 37 } 38 int main() 39 { 40 int T; 41 scanf("%d",&T); 42 while(T--) 43 { 44 int i,j,m,v,e,c; 45 int s[550]; 46 memset(map,0,sizeof(map)); 47 memset(s,0,sizeof(s)); 48 scanf("%d %d",&n,&m); 49 //if(n==0&&m==0) 50 //{ 51 // printf("0 "); 52 // continue; 53 //} 54 for(i=0;i<=n;i++) 55 for(j=0;j<=n;j++) 56 map[i][j]=map[j][i]=200; 57 for(i=0;i<m;i++) 58 { 59 scanf("%d %d %d",&v,&e,&c); 60 map[v][e]=map[e][v]=c; 61 } 62 for(i=0;i<n;i++) 63 scanf("%d",&s[i]); 64 sort(s,s+n); 65 printf("%d ",prim()+s[0]); 66 } 67 return 0; 68 } 69 //prim算法 70 //初始化时没有把 vis数组清零导致 wa