Interesting Application of Binary Searching
| Created | |
|---|---|
| Tags |
What is done?
In, normal binary search we search for first/suitable occurence of the correct answer. Here also we do something similar.
Problem
You are to form an MST such that the no. of edges in the MST that are connected to the index 1 is k which is given.
Solution
We introduce the following idea - to prioritize the edges connected to 1 we add a separate suitable
weight to the edges that have the node 1 in them (during the formation of the MST).
Now we binary search over the suitable weight.
Code
int n, m, k; int net, connections; vi parent, ans; struct node { int u, v, w, weight, index; }; vector<node> edge; bool cmp(node a, node b) { if (a.weight == b.weight) return a.u < b.u; else return a.weight < b.weight; } int Find(int a) { if (parent[a] == a) return a; return parent[a] = Find(parent[a]); } void Union(int mid) { net = 0, connections = 0; for (int i = 1; i <= n; i++) parent[i] = i; for (int i = 0; i < m; i++) { edge[i].weight = edge[i].w; if (edge[i].u == 1) edge[i].weight += mid; } sort(all(edge), cmp); for (int i = 0; i < m; i++) { if (net >= n) break; int a = Find(edge[i].u), b = Find(edge[i].v); int c = connections; if (a != b) { if (edge[i].u == 1) c++; if (c <= k) { ans[++net] = edge[i].index; parent[a] = b; connections = c; } } } } signed main() { cin >> n >> m >> k; parent.resize(n + 1), ans.resize(n + 1), edge.resize(m); vi bandwidth; bandwidth.pb(0); for (int i = 0; i < m; i++) { cin >> edge[i].u >> edge[i].v >> edge[i].w; edge[i].index = i + 1; bandwidth.pb(edge[i].w); if (edge[i].u > edge[i].v) swap(edge[i].u, edge[i].v); } int start = -MAX, end = MAX; while (start < end) { int mid = (start + end + 1) / 2; Union(mid); if (connections == k) start = mid; else end = mid - 1; } Union(start); if (net < n - 1 || connections < k) cout << -1 << endl; else { int sum = 0; for (int i = 1; i <= net; i++) sum += bandwidth[ans[i]]; cout << sum << endl; } return 0; }
Chat that might clear doubts
.png)