Skip to content

Instantly share code, notes, and snippets.

@Sharma96 Sharma96/mst.cpp Secret
Created Sep 20, 2017

Embed
What would you like to do?
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
class dfs{
long int vert,edge;
//map<long int,pair<long int,long int> > m;//u,v,w
vector<pair<long int,pair<long int,long int> > > vec;
//vector<vector<pair<long int,long int> > > vec;
public:
void add(long int u,long int v,long int w){
for(long int ui=0;ui<vec.size();ui++){
pair<long int,long int > PP(u,v),QQ(v,u);
if(vec[ui].second == PP || vec[ui].second == QQ){
//cout<<vec[ui].second.first<< " -- " <<vec[ui].second.second<<endl;
if(vec[ui].first>w){
vec[ui].first = w;
//return;
}
return;
}
}
pair<long int,long int> pq(u,v);
pair<long int,pair<long int,long int> > PQ(w,pq);
vec.push_back(PQ);
//vec[u].push_back(pq);
//vec[v].push_back(pq1);
}
//public:
dfs(long int u,long int v){
vert = u;
edge = v;
//vec.resize(100001);
}
long int find_(long int u,vector<long int> &parent){
if(parent[u] == -1){
return u;
}
return find_(parent[u],parent);
}
void union_(long int u,long int v,vector<long int> &parent){
long int x = find_(u,parent);
long int y = find_(v,parent);
parent[y] = x;
return;
}
void print(){
cout<<"-->"<<endl;
for(long int i=0;i<vec.size();i++){
cout<<vec[i].second.first<<" "<<vec[i].second.second<<" "<<vec[i].first<<endl;
}
cout<<endl;
}
void min_(vector<long int > & le){
//print();
sort(le.begin(),le.end());
sort(vec.begin(),vec.end());
//cout<<"->"<<vec[0].first<<endl;
//print();
//cout<<"->"<<vec[0].first<<endl;
vector<long int>::iterator io = le.begin();
vector<long int> parent(100001,-1);
vector<pair<long int,pair<long int,long int> > >::iterator it = vec.begin();
long int fans = 0;
while(it!=vec.end()){
//long int u =
if(find_(it->second.first,parent) != find_(it->second.second,parent) ){
union_(it->second.first,it->second.second,parent);
if(*io < it->first && io != le.end()){
fans+=*io;
io++;
}
else{
fans += it->first;
}
}
it++;
}
cout<<fans<<endl;
}
};
int main(){
//cout << "Hello World!" << endl;
long int n,m;
cin>>n>>m;
dfs g(n,m);
while(m--){
long int u,v,w;
cin>>u>>v>>w;
g.add(u,v,w);
}
long int q;
cin>>q;
vector<long int> le;
while(q--){
long int we;
cin>>we;
le.push_back(we);
}
g.min_(le);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.