今天是个阴天，下了点雨，work .........
步骤：将所有边排序，然后不断从小到大加上边，这个过程最重要的是避免环的产生，此处用并查集。(nyoj 38)
package 最小生成树; import java.util.Arrays;
import java.util.Scanner;
class Node implements Comparable<Node>
{
int x;
int y;
int val;
public Node(int x,int y,int val)
{
this.x=x;
this.y=y;
this.val=val;
}
@Override
public int compareTo(Node o) {
return this.val-o.val;
} } public class Main { public static void init(int a[])//并查集初始化，用来判断是否有环
{
for(int i=1;i<a.length;i++)a[i]=i; }
public static int find(int a[],int x) //查找节点的父亲,没有优化的方法
{
while(a[x]!=x)
{
x=a[x];
} return x;
}
public static boolean union(int a[],int x,int y)//union一条边
{
int fx=find(a, x);
int fy=find(a, y);
if(fx!=fy)
{
a[fx]=fy;
return true; //成功加入 }
return false;//成环 } public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scn=new Scanner(System.in);
int len=scn.nextInt();
while(len-->0)
{
int ans=0;//保存最后的答案
int v=scn.nextInt();
int e=scn.nextInt();
Node n[]=new Node[e];
for(int i=0;i<e;i++)
{
n[i]=new Node(scn.nextInt(),scn.nextInt(),scn.nextInt()); } Arrays.sort(n);
//并查集的初始化
int father[]=new int[v+1];
init(father);
int index=0;
for(int i=0;i<e;i++)
{
if(union(father, n[i].x,n[i].y))
{ index++; //没成环，加入这条边
ans+=n[i].val; }
if(index==v-1)
{
break;
} }
int min=scn.nextInt(); for(int j=1;j<v;j++)
{
int temp=scn.nextInt();
if(min>temp) min=temp; }
System.out.println(ans+min); } } }