POJ 1251 Jungle Roads 最小生成樹

題意：就是給出你圖，然後求最小生成樹的值即可。注意輸入。

思路：完全裸的最小生成樹，kruskal水之。好久不寫最小生成樹，仔細想了想，還是寫了出來。

代碼：

1. #include
2. #include
3. #include
4. #include
5. #include
6. using namespace std;
7.  
8. #define CLR(arr,val) memset(arr,val,sizeof(arr))
9. const int N = 32;
10. vector vv[N];
11. int numedge,father[N];
12. struct edge{
13. int leftp,rightp,value;
14. }ee[1000];
15. bool cmp(edge a,edge b){
16. return a.value < b.value;
17. }
18. int find(int x){
19. if(x == father[x])
20. return father[x];
21. return find(father[x]);
22. }
23. bool union_set(int lp,int rp){
24. int flp = find(lp);
25. int frp = find(rp);
26. if(flp == frp){
27. return false;
28. }
29. else{
30. father[flp] = frp;
31. return true;
32. }
33. }
34. int kruskal(){
35. int sum = 0;
36. for(int i = 0; i < numedge; ++i){
37. int lp = ee[i].leftp;
38. int rp = ee[i].rightp;
39. if(union_set(lp,rp))
40. sum += ee[i].value;
41. }
42. return sum;
43. }
44. int main(){
45. //freopen(1.txt,r,stdin);
46. int n;
47. while(scanf(%d,&n)&&n){
48. char ch;
49. int num,x;
50. numedge = 0;
51. for(int i = 1; i < n; ++i){
52. cin >> ch;
53. scanf(%d,&num);
54. while(num--){
55. cin >> ch;
56. scanf(%d,&x);
57. int y = (int)(ch - 'A' + 1);
58. ee[numedge].leftp = i;
59. ee[numedge].rightp = y;
60. ee[numedge].value = x;
61. numedge++;
62. }
63. }
64. sort(ee,ee+numedge,cmp);
65. for(int i = 1; i < N; ++i)
66. father[i] = i;
67. int ans = kruskal();
68. printf(%d ,ans);
69. }
70. return 0;
71. }