http://ac.jobdu.com/problem.php?id=1347
第一次做时间这么严格的题目
1.DFS超时
2.并查集判断是否连通，prim求最小生成树，超时
3.并查集判断是否连通，Kruskal求最小生成树，超时
4.并查集+路径压缩判断是否连通，Kruskal求最小生成树，AC
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <queue>
5 #include <algorithm>
6 using namespace std;
7
8 int father[1002];
9
10 int n,m;
11 struct Edge{
12 int st,en,c;
13 };
14 bool cmp(struct Edge a,struct Edge b)
15 {
16 return a.c<b.c;
17 }
18 struct Edge e[10002];
19 int get_father(int n)
20 {
21 if(father[n]==n)
22 return n;
23 else{
24 father[n]=get_father(father[n]);
25 return father[n];
26 }
27 }
28
29 int main()
30 {
31 while(scanf("%d%d",&n,&m)!=EOF)
32 {
33 int i,j;
34 for(i=1;i<=n;i++){
35 father[i]=i;
36 }
37 for(i=1;i<=m;i++){
38 scanf("%d%d%d",&e[i].st,&e[i].en,&e[i].c);
39 }
40 sort(e+1,e+m+1,cmp);
41 int cost=0;
42 for(i=1;i<=m&&n>1;i++){
43 int father_a=get_father(e[i].st);
44 int father_b=get_father(e[i].en);
45 if(father_a!=father_b){
46 father[father_a]=father_b;
47 cost+=e[i].c;
48 n--;
49 }
50 }
51 if(n==1)
52 printf("%d\n",cost);
53 else printf("no\n");
54 }
55 }