Advertisement
Kaidul

Prim's Algorithm

Aug 21st, 2012
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<fstream>
  5. #include<set>
  6. #include<cstring>
  7. #include<algorithm>
  8. using namespace std;
  9. #define Max 100
  10. #define pb push_back
  11. #define READ(f) freopen(f, "r", stdin)
  12. #define WRITE(f) freopen(f, "w", stdout)
  13. #define G struct prims
  14.  
  15. G
  16. {
  17.     int u,v,cost;
  18.     bool operator < (const G& a) const{
  19.         return cost>a.cost;
  20.     }
  21. }p[Max];
  22. priority_queue<G>q,q1,x;
  23. int visited[Max+1];
  24. int main()
  25. {
  26.     READ("in.txt");
  27.     memset(visited,0,sizeof(visited));
  28.     int num_edge,sum=0,src;
  29.     cin>>num_edge;
  30.     for(int i=1;i<=num_edge;i++)
  31.     {
  32.         cin>>p[i].u>>p[i].v>>p[i].cost;
  33.         q.push(p[i]);
  34.     }
  35.      cin>>src;
  36.      visited[src]=1;
  37.      while(!q.empty())
  38.      {
  39.          G pop;
  40.          pop=q.top();
  41.          if((visited[pop.u]) || (visited[pop.v]))
  42.          {
  43.               if((visited[pop.u]) && (visited[pop.v]))
  44.               {
  45.                   q.pop();
  46.                   continue;
  47.               }
  48.                    visited[pop.u]=visited[pop.v]=1;
  49.                    sum+=pop.cost;
  50.                    q.pop();
  51.  
  52.          }
  53.          else
  54.          {
  55.            //q.push(pop);
  56.             //x.push(pop);
  57.  
  58.          }
  59.      }
  60.     //cout<<sum;
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement