SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 79 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top