apl-mhd

Zitu sir assignment

Jan 6th, 2019
161
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<cstdio>
  3. #include <vector>
  4. #include <fstream>
  5. #include <queue>
  6. #include <map>
  7. using namespace std;
  8.  
  9. #define MAX_N 101
  10. #define MAX_M 101
  11.  
  12.  
  13.  
  14.  
  15. /*
  16. minimum spanning tree kruskal
  17.  
  18. 6 8
  19. 0 1 1
  20. 0 2 3
  21. 2 1 3
  22. 2 3 1                    1       6
  23. 1 3 1            (0)------(1)-------(5)
  24.                   |      /  |        |
  25. 3 4 4             |     /   |        |
  26. 1 5 6           3 |   3/    | 1      | 2
  27. 4 5 2             |   /     |        |
  28.                   |  /      |        |
  29.                   | /       |        |
  30.                  (2)------(3)------(4)
  31.                        1        4
  32.  
  33. */
  34.  
  35. /*
  36.                          MST
  37.  
  38.                                 1
  39.                          (0)------(1)      (5)
  40.                                    |        |
  41.                                    |        |
  42.                                    | 1      |  2
  43.                                    |        |
  44.                                    |        |
  45.                                    |        |
  46.                          (2)------(3)------(4)
  47.                                1       4
  48.  
  49. */
  50.  
  51.  
  52. int m,n,wt=0;
  53.  
  54.  
  55. struct Set{
  56.     int parent, rnk;
  57. };
  58.  
  59. struct Edge{
  60.  
  61.     int u, v,w;
  62.  
  63.     bool operator<(const Edge& rhs) const { //sort by weight
  64.  
  65.         return w > rhs.w;
  66.     }
  67.  
  68. };
  69.  
  70. Set S[MAX_N];
  71. Edge E[MAX_M];
  72.  
  73. priority_queue<Edge> q; //minheap data structure
  74. vector<pair<int,int>> mstEdge;
  75. queue<pair<int, int>>e;
  76.  
  77.  
  78.  
  79.  
  80. void read_graph() {
  81.  
  82.  
  83.     for (int i = 0; i <m ; ++i) {
  84.  
  85.         Edge temp;
  86.  
  87.         scanf("%d%d%d",&temp.u, &temp.v, &temp.w);
  88.         q.push(temp);
  89.  
  90.     }
  91.  
  92.  
  93. }
  94.  
  95. void make_set(){
  96.  
  97.     for(int i=0; i<n; i++){
  98.         S[i].parent = i;
  99.         S[i].rnk = 0;
  100.  
  101.     }
  102. }
  103.  
  104.  
  105.  
  106. int find_set(int x){
  107.  
  108.     if(S[x].parent !=x)
  109.         return S[x].parent = find_set(S[x].parent);
  110.     return x;
  111. }
  112.  
  113.  
  114. void link(int u, int v){
  115.  
  116.     if(S[u].rnk > S[v].rnk){
  117.  
  118.         S[v].parent = u;
  119.     }
  120.     else{
  121.  
  122.         S[u].parent = v;
  123.         if(S[u].rnk ==S[v].rnk)
  124.             S[v].rnk++;
  125.  
  126.     }
  127. }
  128.  
  129.  
  130.  
  131. void ds_union(int x, int y, int w){
  132.     int u = find_set(x);
  133.     int v = find_set(y);
  134.  
  135.     if(u != v) {
  136.  
  137.         // cout<<"U : "<<x<<", V : "<<y<<", W : "<<w<<endl;
  138.  
  139.         wt +=w;
  140.         mstEdge.push_back(make_pair(x,y));
  141.  
  142.         link(u, v);
  143.     }
  144.  
  145. }
  146.  
  147.  
  148.  
  149.  
  150.  
  151. void kruskal() {
  152.  
  153.  
  154.     make_set();
  155.  
  156.     while(!q.empty()){
  157.  
  158.  
  159.  
  160.         Edge temp = q.top();
  161.  
  162.         // cout<<temp.u<<" "<<" "<<temp.v<<" "<<temp.w<<endl;
  163.  
  164.         ds_union(temp.u, temp.v,temp.w);
  165.         q.pop();
  166.  
  167.     }
  168.  
  169.  
  170.  
  171. }
  172.  
  173. void print_mst() {
  174.  
  175.  
  176.     cout<<"------Printing MST------\n";
  177.     for (int i = 0; i <mstEdge.size() ; ++i) {
  178.  
  179.         pair<int, int> temp = mstEdge[i];
  180.         cout<<temp.first<<" "<<temp.second<<endl;
  181.     }
  182.  
  183.  
  184.     cout<<"MST cost : "<<wt<<endl;
  185.  
  186. }
  187.  
  188.  
  189. int main() {
  190.  
  191.     freopen("graph.txt", "r", stdin);
  192.  
  193.     cin>>n>>m;
  194.  
  195.     read_graph();
  196.  
  197.     kruskal();
  198.  
  199.     print_mst();
  200.  
  201.  
  202.     return 0;
  203. }
RAW Paste Data