http://poj.org/problem?id=2377
题意为给你一幅图，让你判断图有无最大支撑树，若有则求解图的最大支撑树，若无则输出-1
由于题目给的数据方式用kruskal比较方便，然后我们用已采纳的边数来断定图是否连通，边数=节点数-1
1 #include<stdio.h>
2 #include<algorithm>
3 using namespace std;
4 struct line
5 {
6 int begin;
7 int end;
8 int lenth;
9 };
10 line * amount;
11 int * father;
12 int numofnode,numofline;
13 int i,j,a,b,c;
14 int minlen;
15 int find(int k)
16 {
17 return father[k]==k?k:father[k]=find(father[k]);
18 }
19 int cmp(line a,line b)
20 {
21 return a.lenth>b.lenth?1:0;
22 }
23 void ini()
24 {
25 scanf("%d %d",&numofnode,&numofline);
26 father=new int [numofline+1];
27 amount=new line [numofline];
28 for(i=1;i<=numofnode;i++) father[i]=i;
29 for(i=0;i<numofline;i++)
30 {
31 scanf("%d %d %d",&a,&b,&c);
32 amount[i].begin=a;
33 amount[i].end=b;
34 amount[i].lenth=c;
35 }
36 sort(amount,amount+numofline,cmp);
37 }
38 int kruskal()
39 {
40 minlen=0;
41 int counter=0;
42 for(i=0;i<numofline;i++)
43 {
44 a=find(amount[i].begin),b=find(amount[i].end);
45 if(a!=b)
46 {
47 father[a]=b;
48 minlen+=amount[i].lenth;
49 counter++;
50 }
51 }
52 return counter;
53 }
54 void pr()
55 {
56 int k=kruskal();
57 if(k<numofnode-1) printf("-1\n");
58 else printf("%d\n",minlen);
59 delete [] father;
60 delete [] amount;
61 }
62 int main()
63 {
64 ini();
65 pr();
66 return 0;
67 }