題意：
給出N個(gè)點(diǎn)，若干邊的帶權(quán)無(wú)向圖，然后若干個(gè)點(diǎn)已經(jīng)相連了，求使得整個(gè)圖聯(lián)通的最小代價(jià)。
解法：
這題一般做法是縮點(diǎn)+最小生成樹(shù)，但是由于這題的特殊性，可以不用顯式的縮點(diǎn)，用并查集將已經(jīng)聯(lián)通的點(diǎn)合并后直接使用kustral算法構(gòu)造最小生成樹(shù)，至于判斷圖是否聯(lián)通，一遍DFS判斷點(diǎn)數(shù)是否相等即可。
附帶嗎
1 import java.util.*;
2 import java.io.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static int n=0,m=0,k=0;
9 static int pre[]=new int[501];
10 static int buffer[]=new int[501];
11 static int g[]=new int[501],nxt[]=new int[50001],v[]=new int[50001],c=0;
12 static boolean used[]=new boolean[501];
13 static class edge implements Comparable<edge>
14 {
15 int a,b,v;
16 public int compareTo(edge pos)
17 {
18 return v-pos.v;
19 }
20 }
21 static edge data[]=new edge[25001];
22 static int find(int pos)
23 {
24 if(pre[pos]==pos) return pos;
25 else
26 {
27 pre[pos]=find(pre[pos]);
28 return pre[pos];
29 }
30 }
31 static void insert(int s,int e)
32 {
33 v[c]=e;
34 nxt[c]=g[s];
35 g[s]=c++;
36 }
37 static void dfs(int pos)
38 {
39 if(used[pos]) return;
40 used[pos]=true;
41 for(int p=g[pos];p!=-1;p=nxt[p])
42 dfs(v[p]);
43 }
44 public static void main(String[] args) throws IOException{
45 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
46 in.nextToken();
47 int test=(int)in.nval;
48 for(int i=0;i<data.length;i++)
49 data[i]=new edge();
50 while((test--)!=0)
51 {
52
53 in.nextToken();
54 n=(int)in.nval;
55 in.nextToken();
56 m=(int)in.nval;
57 in.nextToken();
58 k=(int)in.nval;
59 for(int i=0;i<m;i++)
60 {
61 in.nextToken();
62 data[i].a=(int)in.nval;
63 in.nextToken();
64 data[i].b=(int)in.nval;
65 in.nextToken();
66 data[i].v=(int)in.nval;
67 }
68 for(int i=1;i<=n;i++)
69 {
70 pre[i]=i;
71 g[i]=-1;
72 }
73 for(int i=0;i<k;i++)
74 {
75 in.nextToken();
76 int t=(int)in.nval;
77 for(int j=0;j<t;j++)
78 {
79 in.nextToken();
80 buffer[j]=(int)in.nval;
81 }
82 for(int j=1;j<t;j++)
83 pre[find(buffer[0])]=find(buffer[j]);
84 }
85 int total=0;
86 Arrays.sort(data, 0, m);
87 c=0;
88 for(int i=0;i<m;i++)
89 {
90 insert(find(data[i].a),find(data[i].b));
91 insert(find(data[i].b),find(data[i].a));
92
93 }
94
95 Arrays.fill(used,false);
96 int sum=0;
97 for(int i=1;i<=n;i++)
98 used[find(i)]=true;
99 for(int i=1;i<=n;i++)
100 if(used[i]) sum++;
101 Arrays.fill(used,false);
102 dfs(find(1));
103 for(int i=1;i<=n;i++)
104 if(used[i]) sum--;
105 if(sum!=0)
106 {
107 System.out.println(-1);
108 continue;
109 }
110
111 for(int i=0;i<m;i++)
112 if(find(data[i].a)!=find(data[i].b))
113 {
114 pre[find(data[i].a)]=data[i].b;
115 total+=data[i].v;
116 }
117 System.out.println(total);
118 }
119
120 }
121
122 }
123