1040_Donation.md

Algorithm: Minimum Spanning Tree

Problem: Donation

#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);
}
struct edge
{
    int u,v;
    int cost;
    bool operator<(const edge& o)const{
        return cost<o.cost;
    }
};
class DSU{
    public:
    vi par,sz;
    int n;
    DSU(int _n){
        n=_n;
        par.resize(n+1);
        sz.resize(n+1);
        for(int i=0; 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 n,i,j,a;
        cin>>n;
        vector<edge>edges;
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                cin>>a;
                if(a)
                    edges.push_back({i,j,a});
            }
        }
        sort(all(edges));
        int ans=0;
        DSU obj(n);
        for(auto x:edges){
            if(obj.Find(x.u)==obj.Find(x.v)){
                ans+=x.cost;
            }
            else {
                obj.Union(x.u,x.v);
                // cout<<x.u<<" "<<x.v<<endl;
            }
        }
        cout<<"Case "<<cs++<<": ";
        if(obj.sz[obj.Find(0)]!=n){
            cout<<-1<<endl;
        }
        else cout<<ans<<endl;
        
    }

}