Guest User

Untitled

a guest
Oct 23rd, 2019
164
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<queue>
  6. using namespace std;
  7.  
  8. class Record
  9. {
  10. public:
  11. int des;
  12. double w;
  13. };
  14.  
  15. void process();
  16. double Prims(int[1002][1002],int,int,double[1002][1002]);
  17. int arr[1002][1002];
  18. double cost[1002][1002];
  19.  
  20. bool operator<(const Record &a,const Record &b)
  21. {
  22. return a.w>b.w;
  23. }
  24. int main()
  25. {
  26. freopen("in.txt","r",stdin);
  27. process();
  28. return 0;
  29. }
  30. void process()
  31. {
  32. int testCase,i,vertexNum,edgeNum,a,b,c,ind,j;
  33. while(cin>>testCase)
  34. {
  35. if(testCase==0)
  36. break;
  37. for(i=1;i<=testCase;i++)
  38. {
  39. cin>>vertexNum>>edgeNum;
  40. ind=1;
  41. for(j=1;j<=edgeNum;j++)
  42. {
  43. cin>>a>>b>>c;
  44. arr[a][b]=1;
  45. arr[b][a]=1;
  46. cost[a][b]=c;
  47. cost[b][a]=c;
  48. }
  49. double d=Prims(arr,vertexNum,edgeNum,cost);
  50. cout<<d<<endl;
  51. }
  52. }
  53. }
  54. double Prims(int arr[1002][1002],int vertexNum,int edgeNum,double cost[1002][1002])
  55. {
  56. double m,t;
  57. int d[1002],i,j;
  58. priority_queue<Record,vector<Record>,greater<vector<Record>::value_type> >pq;
  59. vector<Record>v;
  60. Record temp;
  61.  
  62. for(i=0;i<=vertexNum;i++)
  63. d[i]=0;
  64. v.clear();
  65. i=1;
  66. for(j=1;j<=vertexNum;j++)
  67. {
  68. if(arr[i][j]==1&&d[j]==0){
  69. temp.des=j;
  70. temp.w=cost[i][j];
  71. v.push_back(temp);
  72. pq.push(v[i-1]);}
  73. }
  74. d[i]=1;
  75. m=0.0;
  76. while(!pq.empty())
  77. {
  78. i=pq.top().des;
  79. t=pq.top().w;
  80. pq.pop();
  81. if(d[i]==0)
  82. {
  83. m=m+t;
  84. cout<<"i: "<<i<<endl;
  85. cout<<"w: "<<t<<endl;
  86. for(j=1;j<=vertexNum;j++)
  87. {
  88. //cout<<"j: "<<j<<" d[j]: "<<d[j]<<endl;
  89. if(arr[i][j]==1&&d[j]==0&&i!=j){
  90. temp.des=j;
  91. cout<<"j: "<<j<<endl;
  92. temp.w=cost[i][j];
  93. cout<<"cost[i][j]: "<<cost[i][j]<<endl;
  94. v.push_back(temp);
  95. pq.push(v[(int)v.size()-1]);}
  96. }
  97. d[i]=1;
  98. }
  99. }
  100. return m;
  101. }
  102.  
  103. in.txt
  104. 1
  105. 9 14
  106. 1 2 4
  107. 1 8 8
  108. 2 3 8
  109. 2 8 11
  110. 3 4 7
  111. 3 6 4
  112. 3 9 2
  113. 4 5 9
  114. 4 6 14
  115. 5 6 10
  116. 6 7 2
  117. 7 8 1
  118. 8 9 7
  119. 9 7 6
RAW Paste Data