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