Solution of Light OJ 1059 - Air Ports

/* 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[10001], n, m; set<int>st; struct edge{ int u, v, w; }one[100001]; bool comp(edge f, edge s){ return f.w<s.w; } int find(int p){ if(pr[p]==p) return p; else return find(pr[p]); } int mst(){ int sm=0, xx, yy, cnt=0; fi(1, n) pr[i]=i; fi(0, m-1){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ pr[yy]=xx; cnt++; sm+=one[i].w; } if(cnt==n-1) return sm; } return sm; } int main(){ int t, c, cs=1, sz, ans, u, v, w, an; cin>>t; while(t--){ an=0; cin>>n>>m>>c; fi(0, m-1){ cin>>u>>v>>w; if(w<c){ one[i].u=u; one[i].v=v; one[i].w=w; } else{ // special case one[i].u=u; one[i].v=u; one[i].w=0; } } sort(one, one+m, comp); ans=mst(); fi(1, n){ st.insert(find(pr[i])); } sz=st.size(); cout<<"Case "<<cs++<<": "<<ans+(sz*c)<<" "<<sz<<endl; st.clear(); } return 0; }

Solution of Light OJ 1041 - Road Construction

/* 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; map<string, string>pr; set<string>st; set<string>::iterator it; int ct, n; struct edge{ string u, v; int w; }one[55]; string find(string p){ while(pr[p]!=p){ p=pr[p]; } return p; } bool comp(edge f, edge s){ return f.w<s.w; } int mst(int st){ int cnt=0, sm=0; string xx, yy; fi(0, n-1){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ pr[yy]=xx; cnt++; sm+=one[i].w; } if(cnt==ct-1)return sm; } return -1; } int main(){ int t, cs=1, w, ans; string u, v; cin>>t; while(t--){ cin>>n; fi(0, n-1){ cin>>u>>v>>w; st.insert(u); st.insert(v); one[i].u=u; one[i].v=v; one[i].w=w; } for(it=st.begin(); it!=st.end(); it++){ pr[*it]=*it; } ct=st.size(); sort(one, one+n, comp); ans=mst(0); cout<<"Case "<<cs++<<": "; if(ans!=-1)cout<<ans<<endl; else cout<<"Impossible"<<endl; st.clear(); pr.clear(); } return 0; }

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

Solution of Light OJ 1029-Civil and Evil Engineer

/* 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 x, pr[105], n; struct edge{ int u, v, w; }one[12005]; bool comp(edge f, edge s){ return f.w<s.w; } int find(int p){ if(pr[p]==p) return p; else return find(pr[p]); } int mst(int st){ int cnt=0, sm=0, xx, yy; fi(0, n)pr[i]=i; fi(0, x-1){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ cnt++; sm+=one[i].w; pr[yy]=xx; } if(cnt==n) break; } return sm; } int mxst(int st){ int cnt=0, sm=0, xx, yy; fi(0, n)pr[i]=i; fd(x-1, 0){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ cnt++; pr[yy]=xx; sm+=one[i].w; } if(cnt==n) break; } return sm; } int main(){ int t, cs=1, u, v, w, up, dwn; cin>>t; while(t--){ cin>>n; x=0; while(1){ cin>>u>>v>>w; if(u==0&&v==0&&w==0) break; one[x].u=u; one[x].v=v; one[x].w=w; x++; } sort(one, one+x, comp); up=mxst(0); dwn=mst(0); cout<<"Case "<<cs++<<": "; if((up+dwn)%2==0) cout<<(up+dwn)/2<<endl; else cout<<up+dwn<<"/"<<2<<endl; } return 0; }