Valmiki's LAN Trouble

Computer Science Level 4

Valmiki Bhavan has a network of $N$ computers connected by $M$ LAN cables. It is guaranteed that any two computers in the network can commute with these $M$ cables. There can be multiple cables connecting $2$ computers. A computer may be connected via a cable to itself. We say that computer $A$ can communicate with computer $B$ , if there exists a sequence of cables connecting these $2$ computers directly or indirectly. Each cable has a latency associated with it. Now, SWD have asked the intelligent Addy to revamp the existing network( with treat assured which Addy loves more than anything) and replace some existing cables with newer cables. He is given $Q$ new cables, each having its own latency. He can pick any number of cables (maybe $0$ ) from these $Q$ cables and use it to replace any cable in the existing network. Each new cable can be used at most once. It is not necessary to replace every cable from the existing network. Now, considering he uses an arbitrary number of new cables and embeds them into the existing network, he needs to pick $N \ - \ 1$ cables from this network (can consist of old as well as new ) such that using these $N \ - \ 1$ cables, it is possible to communicate between any $2$ computers present in the network. What can be the minimum sum of latencies of these $N-1$ cables satisfying the above constraints, considering he performs the replacement of the cables optimally?

Input format

The first line of input consists of two integers $N$ and $M$ . Next $M$ lines consists of three integers each: $A$ , $B$ and $L$ denoting a cable between computers $A$ and $B$ having latency $L$ . Note that the computers are labelled from $1$ to $N$ .Next line consists of an integer $Q$ denoting the number of cables available for use. Next line consists of an array $C$ denoting the latencies of the $Q$ cables.

Given below is the link to the test file. Your answer is the sum of latencies of all cables in the most optimal network possible.

Test file

The answer is 82862.

1 solution

Kunal Verma
Nov 29, 2017

Use Kruskal to find the minimum spanning tree, push the edges to the MST into a list and then greedily replace the cables from highest to lowest in the MST greedily with new cables of the lowest possible latencies given in the additional list.

#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define MOD 1000000007
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

//KunalVerma@BPHC

using namespace std;

ll id[100000],nodes,edges,q;
pair<ll,pair<ll,ll>>p[100000];
ll extras[100000];
vector<ll>cost;

void initialize()
{
    for(ll i=0;i<100000;i++)
        id[i]=i;
}

ll root(int x)
{
    while(x!=id[x])
    {
        id[x]=id[id[x]];
        x=id[x];
    }
    return x;
}

void union1(ll x,ll y)
{
    id[root(x)]=id[root(y)];
}

void kruskal(pair<ll,pair<ll,ll>>p[])
{
    ll temp=0;
    for(ll i=0;i<edges;i++)
    {
        if(root(p[i].second.first)!=root(p[i].second.second))
        {
            cost.push_back(p[i].first);
            union1(p[i].second.first,p[i].second.second);
        }
    }
}

int main()
{
    IOS;
    initialize();
    cin >> nodes >> edges;
    for(ll i=0;i<edges;i++)
    {
        ll x,y;
        ll w;
        cin >> x >> y >> w;
        p[i].first=w;
        p[i].second.first=x;
        p[i].second.second=y;
    }
    cin >> q;
    for(ll i=0;i<q;i++)
        cin >> extras[i];
    sort(extras,extras+q);
    ll tt=0;
    sort(p,p+edges);
    kruskal(p);
    sort(cost.begin(),cost.end());
    for(ll i=cost.size()-1;i>=0&&tt<q;i--)
    {
        if(cost[i]>extras[tt])
        {
            cost[i]=extras[tt];
            tt++;
        }
    }
    ll sum=0;
    for(ll i=0;i<cost.size();i++)
        sum+=cost[i];
    cout << sum;
}

This gives the answer as $\boxed{82862}$

Why 100000 when there's only 100 computers?

Christopher Boo - 3 years, 6 months ago

Loops are allowed. Just not self. Cables can be connected in parallel.

Kunal Verma - 3 years, 6 months ago

Valmiki's LAN Trouble

The answer is 82862.

1 solution

0 pending reports