问题 H: 小区的路

时间限制: 1Sec  内存限制: 128MB

提交: 21  解决: 6

[][][]

题目描述

你作为一名精通算法的程序员，被某公司聘请到开发区协助建设小区。小区已经建设N（1<N<100，编号1-N）幢大楼，计划任意两个大楼都能直接或间接到达，且已经对修建某些大楼之间的路做了很多预算，施工前，开发商又打算建造一座公园，而且计划每个大楼的人都能直接或者间接通过大路走到公园，同样做好了所有预算，现在让你来计算实现需求至少需要花费多少资金。

输入

第一行输入T（0<T<=100），表示测试数据的数量,接下来是两个数N，M，分别表示大楼的个数，做过预算的路的条数，接下来有N个数，第i 个数字表示第i 座大楼直接连接到公园需要的资金，接下来M行，每行包括三个数字a,b,c，表示大楼a 和b 修路，需要花费资金为c。

输出

对每组数据测试数据，输出满足大楼和公园能相互到达需要的最少资金。

样例输入

2

3 2

10 5 8

1 2 5

1 3 6

3 1

10 5 8

1 2 6

样例输出

16

19

#include 
     
       #include 
      
        #include 
       
         #define MAXN 1000 using namespace std; struct node{     int v;     int u;     int cost;     int st; }g[MAXN]; int per[MAXN]; bool cmp(node g1, node g2) {     return g1.cost < g2.cost; } int find(int x) {     if(x == per[x]) return x;     else return per[x] = find(per[x]); } int main() {     int n, m, t, c;     scanf("%d", &t);     while(t--)     {         scanf("%d%d", &n, &m);         int val = 0;         int w = n + m;         for (int i = 0; i <= n; i++) {             per[i] = i;         }         for (int i = 1; i <= n; i++) {             g[i + m].u = 0;             g[i + m].v = i;             scanf("%d", &c);             g[i + m].cost = c;         }         for(int i = 1; i <= m; i++)         {             scanf("%d%d%d", &g[i].u, &g[i].v, &g[i].cost);         }         sort(g + 1, g + 1 + w, cmp);         for(int i = 1 ;i <= w; i++){             int fx = find(g[i].u);             int fy = find(g[i].v);             if(fx != fy) {                 val += g[i].cost;                 per[fy] = fx;             }         }         printf("%d\n",val);     }     return 0; }