# Interesting Application of Binary Searching

Created @Nov 28, 2020 12:22 PM

## 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;
}