nyoj-布线问题

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;

const int Max = 2000000;

struct ed
{
       int u;
       int v;
       int w;
};
ed e[Max];

int f[Max];
int x[Max];

bool cmp(ed a,ed b)
{
    if(a.w<b.w)
     return true;
    else
      return false;
}

int getf(int v)
{
    if(f[v] == v)
      return v;
    else
    {
       f[v] = getf(f[v]);
       return f[v];
    }
}
int merge(int u,int v)
{
    int t1,t2;
    t1 = getf(f[u]);
    t2 = getf(f[v]);
    if(t1 != t2)
    {
          f[t2] = t1;
          return 1;
    }
    return 0;
}
int main()
{
    int n;
    cin >> n;
    int vn,en;
    while(n--)
    {
              int sum = 0;
              int count = 0;
              int minele;
              cin >> vn >> en;
              for(int i = 0; i < en; i++)
                cin >> e[i].u >> e[i].v >> e[i].w;
             
              for(int i = 0; i < vn; i++)
                 cin >> x[i];
              
               minele = *min_element(x,x+vn); 
              
               sort(e,e+en,cmp);       //按权值排序 
               
               for(int i = 1; i <= vn; i++)
                 f[i] = i;
               for(int i = 0; i < en; i++)
               {
                    if(merge(e[i].u,e[i].v))
                    {                       //若u和v不连通 
                         count ++;
                         sum = sum + e[i].w;
                    }
                    if(count == vn-1)
                    { 
                         break;
                    }
                }
                cout << sum + minele << endl;
       }
       return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
const int Max = 550;
const int inf = 999999999;
int dis[Max] ;
int e[Max][Max];
int book[Max];
int x[Max];

int main()
{
     int  n;
     int vn,en;
     cin >> n;

     while(n--)
     {
              cin >> vn >> en;
               for(int i =1;  i <= vn ;i++)
                 for(int j = 1; j <= vn ;j++)
                  e[i][j] = inf;
               memset(book,0,sizeof(book));
               int a,b,c;
               int sum = 0;
               int count = 1;
            
               for(int i = 0;i < en;i++)
               { cin >> a >> b >> c;
                 e[a][b] = c;
                 e[b][a] = c;
                 }
               for(int i = 0; i  < vn; i++)
                   cin >> x[i];
               int minele = *min_element(x,x+vn);
                 
               for(int i =1  ; i <= vn;i++)
                dis[i] = e[1][i];
                book[1] = 1;
                while(count < vn)
                {
                            int mini  = inf;
                            int j;
                            for(int i = 1; i <= vn;i ++)
                               if(book[i]==0&&dis[i] < mini)
                                  {
                                       
                                           mini = dis[i];
                                           j = i;
                                  }
                            sum = sum + dis[j];      
                            book[j] = 1;
                            count++;
                            for(int i = 1; i <= vn; i++)
                              if(dis[i] > e[j][i])  //更新顶点i到树的最短距离
                                 dis[i] = e[j][i];
                }
                       cout << sum + minele << endl;
                       }
                 return 0;
                 }