布线问题

时间限制：

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

//代码一：克鲁斯卡尔算法（超时） #include
        
          #include
         
           #include
          
            #include
           
          
         
        

struct edge {
       int v1;  int v2;  int c; }t; int v,e,sum;

int find(int father[],int v) {
       int temp=v;  while(father[temp]>0)   temp=father[temp];  return temp; }

void Kruskal(struct edge edges[],int n) {
       int i,j,vf1,vf2;  int father[501];  memset(father,-1,sizeof(father));  i=0;  j=0;  while(i
        

int main() {
       int n,k,i,j,min;  struct edge *edges;  scanf("%d",&n);  while(n--)  {
        sum=0;   min=0x3fffffff;   scanf("%d%d",&v,&e);   edges=(struct edge*)malloc(e*sizeof(struct edge));   for(i=0;i
        
         =0;--i)    for(j=0;j
         
          edges[j+1].c)     {
           t=edges[j];      edges[j]=edges[j+1];      edges[j+1]=t;     }   Kruskal(edges,v);   for(i=0;i
          
            #include
           
             void prim(int**map,int n); int sum;
           
          
         
        

int main() {
       int n,i,j,min,a,b,c,e,v;  int **map;  scanf("%d",&n);  while(n--)  {
        sum=0;   min=0x7fffffff;   scanf("%d%d",&v,&e);   map=(int **)malloc((v+1)*sizeof(int*));//邻接矩阵   for(i=0;i<=v;++i)    map[i]=(int *)malloc((v+1)*sizeof(int));   for(i=0 ; i<=v ;++i)     for(j=i+1;j<=v;++j)      map[i][j]=map[j][i]=0x7fffffff;    for(i=0;i
        
         map[k][j])      lowcost[j]=map[k][j];    }       } }