Solution of Light OJ 1040 - Donation

/* Bismillahir Rahmanir Rahim Solution using (MST)Kruskal's algorithm. */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) using namespace std; int pr[55], k, n; struct edge{ int u, v, w; }one[2509]; bool comp(edge f, edge s){ return f.w<s.w; } int find(int p){ if(p==pr[p]) return p; else return find(pr[p]); } int mst(){ fi(1, n)pr[i]=i; int cost=0, cnt=0, xx, yy; fi(0, k-1){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ cnt++; cost+=one[i].w; pr[yy]=xx; } if(cnt==n-1) return cost; } return -1; } int main(){ int t, total, cs=1, ans, w; cin>>t; while(t--){ total=0, k=0; cin>>n; fi(1, n){ for(int j=1; j<=n; j++){ cin>>w; total+=w; if(i!=j&&w){ one[k].u=i; one[k].v=j; one[k].w=w; k++; } } } sort(one, one+k, comp); ans=mst(); cout<<"Case "<<cs++<<": "; if(n==1)cout<<total<<endl; // its special case else if(ans==-1)cout<<"-1"<<endl; else cout<<total-ans<<endl; } return 0; }