Light OJ 1040 - Donation

Problem link - 1040 - Donation

Its a very basic mst problem.

let us try to analyze some test case

2

27 26

1 52

here 

we can see if we keep only the cable with 1 meter then all rooms are connected and we can donate all other cables so the answer becomes (27+26+52+1) - 1 = 105

stdout

Case 1: 105

4

0 1 0 0

1 0 0 0

0 0 0 1

0 0 1 0

here
All rooms are not connected  by a single path so the output will be - 1

	#include<bits/stdc++.h>
	using namespace std;
	int rep[60];
	struct edge{
	int a,b,c;
	}arr[3000];
	void makeset(int n){
	for(int i=1;i<=n;i++){
	rep[i]=i;
	}
	}
	bool cmp(edge x,edge y){
	return x.c<y.c;
	}
	int finder(int x){
	if(rep[x]==x) return x;
	return rep[x]=finder(rep[x]);
	}
	int main(){
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
	int n,to=0;
	cin>>n;
	int y=0;
	for(int k=1;k<=n;k++){
	for(int j=1;j<=n;j++){
	int a;
	cin>>a;
	if(a==0) continue;
	arr[y].a=k;
	arr[y].b=j;
	arr[y].c=a;
	to=to+a;
	y++;
	}
	}
	makeset(n);
	sort(arr,arr+y,cmp);
	int sum=0;
	int edg=0;
	for(int q=0;q<y;q++){
	int x = finder(arr[q].a);
	int y = finder(arr[q].b);
	if(x!=y){
	rep[x]=y;
	edg++;
	sum = sum+ arr[q].c;
	}
	}
	if(edg!=n-1){
	printf("Case %d: -1\n",i);
	}
	else{
	printf("Case %d: %d\n",i,to-sum);
	}
	}
	}

view raw 1040 - Donation.cpp hosted with ❤ by GitHub