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