1041_Road_Construction.md

Algorithm: Minimum Spanning Tree

Problem: 1041 Road Construction

#include <bits/stdc++.h>
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
#define ll long long
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
int Set(int N, int pos) {return  N = N | (1<<pos);}
int Reset(int N, int pos) {return  N = N & ~(1<<pos);}
bool Cheek(int N, int pos) {return  (bool)(N & (1<<pos));}
#define least_one_pos(x) __builtin_ffs(x)
#define leading_zeros(x) __builtin_clz(x)
#define tailing_zeros(x) __builtin_ctz(x)
#define num_of_one(x) __builtin_popcount(x)
///............x...........///
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define UNIQUE(X) (X).erase(unique(all(X)), (X).end())
#define ft cout << "for test"<<endl;
#define print(v) for (auto it : v)cout << it<<" ";cout << endl;
#define PI acos(-1.0)
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define t_c int test, cs = 1;cin>>test;while (test--)
///................function.....................///

//#define mod 1000000007
//........constant........///
const ll N = 1e6+5;
void file(){
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
}
class DSU{
    public:
    vi par,sz;
    int n;
    DSU(int _n){
        n=_n;
        par.resize(n+1);
        sz.resize(n+1);
        for(int i=1; i<=n; i++)par[i]=i,sz[i]=1;
    }
    int Find(int a){
        if(a==par[a])return par[a];
        return par[a] = Find(par[a]);
    }
    void Union(int a, int b){
        a = Find(a);b = Find(b);
        if(a==b)return;
        if(sz[a]>=sz[b]){
            sz[a]+=sz[b];
            par[b]=a;
        }
        else{
            par[a]=b;
            sz[b]+=sz[a];
        }
    }
};
int main(){
    FIO;
    // file();
    t_c{
        int m,i,j;
        cin>>m;
        vector<pair<pair<string,string>,int>>v(m);
        map<string,int>cast;
        int shuru=1;
        for(i=0; i<m; i++){
            string a,b;
            int c;
            cin>>a>>b>>c;
            if(cast.find(a)==cast.end())cast[a]=shuru++;//,cout<<a<<" "<<shuru-1<<endl;
            if(cast.find(b)==cast.end())cast[b]=shuru++;//,cout<<b<<" "<<shuru-1<<endl;
            v[i]={{a,b},c};
        }
        DSU obj(shuru);
        vector<pair<int,pair<int,int>>>edges;
        for(auto x:v){
            int a = cast[x.first.first];
            int b = cast[x.first.second];
            int c = x.second;
            edges.push_back({c,{a,b}});
        }
        sort(all(edges));
        int ans=0;
        for(auto x:edges){
            int a = x.second.first;
            int b = x.second.second;
            int c = x.first;
            if(obj.Find(a)!=obj.Find(b)){
                ans += c;
                // cout<<a<<" "<<b<<endl;
                obj.Union(a,b);
            }
        }
        cout<<"Case "<<cs++<<": ";
        // cout<<obj.sz[obj.Find(1)]<<endl;
        if(obj.sz[obj.Find(1)]!=shuru-1)cout<<"Impossible"<<endl;
        else cout<<ans<<endl;
    }

}