程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1251 Jungle Roads 最小生成樹

POJ 1251 Jungle Roads 最小生成樹

編輯:C++入門知識

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. }

     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved