mst.cpp

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