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

POJ 2421 Constructing Roads 最小生成樹

編輯:C++入門知識

POJ 2421 Constructing Roads 最小生成樹


題意:還是給你n個點,然後求最小生成樹。特殊之處在於有一些點之間已經連上了邊。

思路:對於已經有邊的點,特殊標記一下,加邊的時候把這些邊的權值賦值為0即可。這樣就可以既保證這些邊一定存在,又保證了所求的結果正確。

代碼:

 

  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 = 110;
  10. int father[N];
  11. struct edge{
  12. int lp,rp,value;
  13. }ee[N*N];
  14. int map[N][N],flag[N][N],numedge,n;
  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 x,int y){
  24. int fx = find(x);
  25. int fy = find(y);
  26. if(fx == fy){
  27. return false;
  28. }
  29. else{
  30. father[fx] = fy;
  31. return true;
  32. }
  33. }
  34. int kruskal(){
  35. sort(ee,ee+numedge,cmp);
  36. for(int i = 1; i <= n; ++i)
  37. father[i] = i;
  38. int sum = 0;
  39. for(int i = 0; i < numedge; ++i){
  40. int lx = ee[i].lp;
  41. int rx = ee[i].rp;
  42. if(Union_Set(lx,rx)){
  43. sum += ee[i].value;
  44. }
  45. }
  46. return sum;
  47. }
  48. int main(){
  49. //freopen(1.txt,r,stdin);
  50. while(scanf(%d,&n) != EOF){
  51. CLR(flag,0);
  52. for(int i = 1; i <= n; ++i){
  53. for(int j = 1; j <= n; ++j)
  54. scanf(%d,&map[i][j]);
  55. }
  56. int m,x,y;
  57. scanf(%d,&m);
  58. while(m--){
  59. scanf(%d%d,&x,&y);
  60. flag[x][y] = 1;
  61. }
  62. numedge = 0;
  63. for(int i = 1; i < n; ++i){
  64. for(int j = i + 1; j <= n; ++j){
  65. if(flag[i][j]){
  66. ee[numedge].lp = i;
  67. ee[numedge].rp = j;
  68. ee[numedge].value = 0;
  69. numedge++;
  70. }
  71. else{
  72. ee[numedge].lp = i;
  73. ee[numedge].rp = j;
  74. ee[numedge].value = map[i][j];
  75. numedge++;
  76. }
  77. }
  78. }
  79. int ans = kruskal();
  80. printf(%d ,ans);
  81. }
  82. return 0;
  83. }

     

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