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

Solution of Light OJ 1002-Country Roads

/* Bismillahir Rahmanir Rahim Solution using BFS 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--) #define inf 100009 using namespace std; vector<int>vt[505], cost[505]; int dis[505]={0}; void bfs(int st){ queue<int>q; q.push(st); dis[st]=0; int p, sz, temp, xx; while(!q.empty()){ p=q.front(); q.pop(); sz=vt[p].size(); fi(0, sz-1){ xx=vt[p][i]; temp=max(dis[p], cost[p][i]); if(temp<dis[xx]){ dis[xx]=temp; q.push(xx); } } } } int main(){ int t, cs=1, n, m, u, v, w, tt; cin>>t; while(t--){ cin>>n>>m; fi(0, m-1){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } cin>>tt; fi(0, n-1) dis[i]=inf; bfs(tt); cout<<"Case "<<cs++<<":"<<endl; fi(0, n-1){ if(dis[i]==inf)cout<<"Impossible"<<endl; else cout<<dis[i]<<endl; } fi(0, n-1){ vt[i].clear(); cost[i].clear(); } } return 0; }

Kruskal's Algorithm - Implementation with C++

/* Bismillahir Rahmanir Rahim Implementation of (MST)Kruskal's algorithm with C++ */ #include<bits/stdc++.h> #define fi(i, n) for(int i=0; i<n; i++) using namespace std; struct node{ // structure int u, v, cost; }; int pr[101], edge, n; node one[100]; bool comp(node f, node s){ // sort of structure return f.cost<s.cost; } int find(int p){ // Disjoint Set if(pr[p]==p)return p; else return find(pr[p]); } int mst(int st){ // minimum-cost spanning tree fi(i, n) pr[i]=i; int cnt=0, xx, sm=0, yy; fi(i, edge){ xx=find(one[i].u); // parent of one[i].u yy=find(one[i].v); if(xx!=yy){ pr[yy]=xx; cnt++; sm+=one[i].cost; } if(cnt==n-1) break; } return sm; } int main(){ int u, v, cost; /* input start */ cin>>n>>edge; fi(i, edge){ cin>>u>>v>>cost; one[i].u=u; one[i].v=v; one[i].cost=cost; } sort(one, one+edge, comp); cout<<mst(1)<<endl; return 0; }

BFS Algorithm - Implementation with C++

/* Bismillahir Rahmamir Rahim Implementing BFS algorithm with c++ */ #include<bits/stdc++.h> using namespace std; vector<int>vt[100]; queue<int>q; int cost[100][100], dis[100], visit[100]; void bfs(int st){ for(int i=0; i<=100; i++){ dis[i]=100009, visit[i]=0; } int p, y, cst; dis[st]=0; q.push(st); while(!q.empty()){ p=q.front(); q.pop(); if(!visit[p]){ for(int i=0; i<vt[p].size(); i++){ y=vt[p][i]; cst=cost[p][y]+dis[p]; if(cst<dis[y]){ dis[y]=cst; q.push(y); } } visit[p]=1; } } } int main(){ int n1, n2, edge, c, x; cin>>edge; for(int i=0; i<edge; i++){ cin>>n1>>n2>>c; vt[n1].push_back(n2); vt[n2].push_back(n1); cost[n1][n2]=cost[n2][n1]=c; } bfs(1); while(cin>>x) cout<<dis[x]<<endl; return 0; }