HDOJ---1233やはりスムーズエンジニアリング[primアルゴリズム||Kruskalアルゴリズム]

やはりスムーズな工事です
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 14115    Accepted Submission(s): 6435
Problem Description
ある省は田舎の交通状況を調査し、得られた統計表には任意の2つの村間の距離がリストされている.省政府の「円滑な工事」の目標は、全省のどの2つの村の間でも道路交通を実現できるようにすることである(しかし、直接的な道路がつながっているとは限らず、間接的に道路を通過すればよい)、敷設された道路の総長さを最小限に抑えることを要求している.最小の道路の全長を計算してください.
 
 
Input
テスト入力には、いくつかのテスト例が含まれます.各試験例の1行目は、村の数N(<100)を与える.その後のN(N−1)/2行は村間の距離に対応し,各行には2つの村の番号とこの2つの村間の距離のペアの正の整数を与えた.簡単にするために、村は1からN番までです.
Nが0の場合、入力は終了し、この例は処理されない.
 
 
Output
各試験例について、1行に最小の道路総長を出力する.
 
 
Sample Input
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
 
 
Sample Output
3 5
Hint
Hint
Huge input, scanf is recommended.
 
 
Source
浙大コンピュータ大学院生の再試験の上機試験-2006年
 
 
Recommend
JGShining
 
 
 
 
 
 Kruskalアルゴリズム
code:

 1 #include <iostream>   

 2 #include <iomanip>   

 3 #include <fstream>   

 4 #include <sstream>   

 5 #include <algorithm>   

 6 #include <string>   

 7 #include <set>   

 8 #include <utility>   

 9 #include <queue>   

10 #include <stack>   

11 #include <list>   

12 #include <vector>   

13 #include <cstdio>   

14 #include <cstdlib>   

15 #include <cstring>   

16 #include <cmath>   

17 #include <ctime>   

18 #include <ctype.h> 

19 using namespace std;

20 

21 #define MAXN 101

22 

23 int father[MAXN];   

24 int n;

25 int cnt;           //         

26 int sum;           //     

27 

28 typedef struct edge

29 {

30     int x,y;

31     int len;

32 }Edge;

33 

34 Edge edge[MAXN*MAXN]; 

35 

36 int cmp(const Edge &a,const Edge &b)

37 {

38     return a.len<b.len;

39 }

40 

41 int findset(int v)

42 {

43     return father[v];

44 }

45 

46 void merget(int a,int b)

47 {

48     int i;

49     for(i=1;i<=n;i++)

50         if(father[i]==a)

51             father[i]=b;

52 }

53 

54 int main()

55 {

56     int i;

57     int m;

58     int tempx,tempy;

59     while(~scanf("%d",&n),n)                 //n     

60     {

61         cnt=0;

62         sum=0;

63         m=((n-1)*n)>>1;                      //  m  

64         memset(edge,0,sizeof(edge));

65         for(i=1;i<=n;i++)

66             father[i]=i;

67         for(i=0;i<m;i++)

68             scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].len);

69         sort(edge,edge+i,cmp);                //      

70         for(i=0;i<m&&cnt!=n;i++)

71         {

72             tempx=findset(edge[i].x);

73             tempy=findset(edge[i].y);

74             if(tempx!=tempy)

75             {

76                 merget(tempx,tempy);

77                 cnt++;

78                 sum+=edge[i].len;

79             }

80         }

81         printf("%d
",sum);

82     }

83     return 0;

84 }

 
 
 
 
 
 
 
Primアルゴリズム:
code:

 1 #include <iostream>   

 2 #include <iomanip>   

 3 #include <fstream>   

 4 #include <sstream>   

 5 #include <algorithm>   

 6 #include <string>   

 7 #include <set>   

 8 #include <utility>   

 9 #include <queue>   

10 #include <stack>   

11 #include <list>   

12 #include <vector>   

13 #include <cstdio>   

14 #include <cstdlib>   

15 #include <cstring>   

16 #include <cmath>   

17 #include <ctime>   

18 #include <ctype.h> 

19 using namespace std;

20 

21 #define MAXN 101

22 

23 int map[MAXN][MAXN];

24 int vst[MAXN];

25 int dis[MAXN];

26 int n;

27 

28 int prim()

29 {

30     

31     int i,j,k;

32     int min,sum=0;

33     memset(vst,0,sizeof(vst));

34     for(i=1;i<=n;i++)           

35         dis[i]=map[1][i];

36     vst[1]=1;

37     for(i=2;i<=n;i++)

38     {

39         k=1;

40         min=INT_MAX;

41         for(j=2;j<=n;j++)

42             if(dis[j]<min&&!vst[j])               

43             {

44                 min=dis[j];

45                 k=j;

46             }

47         sum+=min;

48         vst[k]=1;

49         for(j=1;j<=n;j++)

50             if(map[k][j]<dis[j])

51                 dis[j]=map[k][j];

52     }

53     return sum;

54 }

55 

56 int main()

57 {

58     int i,j;

59     int m;

60     int tempx,tempy,templen;

61     int cost;

62     while(~scanf("%d",&n),n)

63     {

64         m=(n*(n-1))>>1;

65         for(i=1;i<=m;i++)

66         {

67             scanf("%d%d%d",&tempx,&tempy,&templen);

68             map[tempx][tempy]=templen;

69             map[tempy][tempx]=templen;

70         }

71         printf("%d
",prim());

72     }

73     return 0;

74 }