SHARE
TWEET

Untitled

a guest May 21st, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct Edge
  6. {
  7.     int u, v, weight;
  8. };
  9.  
  10. struct G
  11. {
  12.     int V, E;
  13.     Edge* edges;
  14. };
  15.  
  16.  
  17. struct subset
  18. {
  19.     int rank;
  20.     int parent;
  21. };
  22.  
  23.  
  24. int find(subset subsets[], int i)
  25. {
  26.     if(subsets[i].parent!=i)
  27.     {
  28.         i=find(subsets, subsets[i].parent);
  29.     }
  30.     return subsets[i].parent;
  31. }
  32.  
  33. void Union(subset subsets[], int a, int b)
  34. {
  35.     int x=find(subsets, a);
  36.     int y=find(subsets, b);
  37.     if(x!=y)
  38.     {
  39.         if(subsets[x].rank<subsets[y].rank) subsets[x].parent=y;
  40.         else
  41.         {
  42.             subsets[y].parent=x;
  43.             if(subsets[x].rank==subsets[y].rank) subsets[x].rank++;
  44.         }
  45.     }
  46. }
  47.  
  48. int Partition(Edge t[], int p, int r)
  49. {
  50.     int x=t[r].weight;
  51.     int i, j;
  52.     i=p-1;
  53.     for(j=p; j<r; j++)
  54.     {
  55.         if(t[j].weight<x)
  56.         {
  57.             i++;
  58.             swap(t[i], t[j]);
  59.         }
  60.     }
  61.     swap(t[i+1], t[r]);
  62.     return i+1;
  63. }
  64.  
  65. void qSort(Edge t[], int p, int r)
  66. {
  67.     if(p<r)
  68.     {
  69.         int q=Partition(t, p, r);
  70.         qSort(t, p, q-1);
  71.         qSort(t, q+1, r);
  72.     }
  73. }
  74.  
  75. int Kruskal(G* graph)
  76. {
  77.     qSort(graph->edges, 0, graph->E-1);
  78.     subset* subsets=new subset[graph->V];
  79.     for(int v=0; v<graph->V; v++)
  80.     {
  81.         subsets[v].parent=v;
  82.         subsets[v].rank=0;
  83.     }
  84.     int e=0;
  85.     int result=0;
  86.     for(int i=0; i<graph->E && e<graph->V-1; i++)
  87.     {
  88.         int x=find(subsets, graph->edges[i].u);
  89.         int y=find(subsets, graph->edges[i].v);
  90.         if(x!=y)
  91.         {
  92.             result+=graph->edges[i].weight;
  93.             Union(subsets, x, y);
  94.         }
  95.     }
  96.     return result;
  97. }
  98.  
  99. int two_minimum(Edge tab[], int n)
  100. {
  101.     int x=INT_MAX, y=INT_MAX;
  102.     for(int i=0; i<n; i++)
  103.     {
  104.         if(tab[i].weight<x) x=tab[i].weight;
  105.         else if(tab[i].weight<y && tab[i].weight>=x) y=tab[i].weight;
  106.     }
  107.     return x+y;
  108. }
  109.  
  110. int Low_bound(G graph)
  111. {
  112.     int lbound=0;
  113.     int Edg=0;
  114.     int current;
  115.     for(int i=0; i<graph.V; i++)
  116.     {
  117.         for(int j=0; j<graph.E; j++)
  118.         {
  119.             if(graph.edges[j].u!=i && graph.edges[j].v!=i) Edg++;
  120.         }
  121.         G* new_graph=new G;
  122.         new_graph->E=Edg;
  123.         new_graph->V=graph.V-1;
  124.         new_graph->edges=new Edge[new_graph->E];
  125.         int x=0;
  126.         int y=0;
  127.         Edge* Deleted_Edges=new Edge [graph.E-Edg];
  128.         for(int j=0; j<graph.E; j++)
  129.         {
  130.             if(graph.edges[j].u!=i && graph.edges[j].v!=i)
  131.             {
  132.                 new_graph->edges[x++]=graph.edges[j];
  133.             }
  134.             else Deleted_Edges[y++]=graph.edges[j];
  135.         }
  136.         current=Kruskal(new_graph);
  137.         current+=two_minimum(Deleted_Edges, graph.E-Edg);
  138.         if(current>lbound) lbound=current;
  139.         delete[]new_graph->edges;
  140.         delete[]Deleted_Edges;
  141.         delete new_graph;
  142.     }
  143.     return lbound;
  144. }
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