UVa – 11631 – Dark Roads

Problem Link: https://onlinejudge.org/external/116/11631.pdf

Note: This problem is a simple implementation of the Minimum Spanning Tree(MST) with a very simple tweak. I applied Prim’s algorithm here, Krushkal’s algorithm can also be used.

Code:

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <new>
#include <map>
#include <unordered_map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>


using namespace std;

int Prims(vector<vector<pair<int, int> > > &edges, int node)
{
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >pq;
    int vis[200005]= {0};
    int ans=0;
    int nodes_added=0;
    pq.push({0,0});
    while(nodes_added<node)
    {
        int from=pq.top().second;
        int cost=pq.top().first;
        pq.pop();
        if(!vis[from])
        {
            nodes_added++;
            vis[from]=1; //added to MST
            ans+=cost;
            for(int i=0; i<edges[from].size(); i++)
            {
                pair<int,int> to=edges[from][i];
                pq.push(to);
            }
        }
    }
    return ans;
}

int main()
{
    int node, edge;
    while(cin>>node>>edge)
    {
        if(node==0 && edge==0) break;
        vector<vector<pair<int, int> > > edges(node);
        int total_cost = 0;
        for(int i=0; i<edge; i++) //Building adjacency graph
        {
            int x,y,cost;
            cin>>x>>y>>cost;
            edges[x].push_back({cost, y});
            edges[y].push_back({cost, x});
            total_cost+=cost;
        }
        int ans=Prims(edges, node);
        cout<<total_cost-ans<<endl;
    }
    return 0;
}

Leave a comment