• API
• FAQ
• Tools
• Archive
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.

Top