Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * E:\Dropbox\Profession\SUST\CSE_138_2017\Kruskal.cpp
- * Created on: 2017-11-22-16.37.51, Wednesday
- * Verdict: Not Solved
- * Author: Enamul Hassan
- **/
- #include <bits/stdc++.h>
- #define _ ios_base::sync_with_stdio(0);cin.tie(0);
- #define SZ(a) ((ll)a.size())
- #define sz 200005
- #define pb push_back
- #define pp pop_back()
- #define all(a) a.begin(),a.end()
- #define ll long long
- #define cntbit(mask) __builtin_popcount(mask)
- #define unify(a) stable_sort(a.begin(),a.end());a.resize(distance(a.begin(),unique(all(a))));
- #define fread freopen("input.txt","r",stdin)
- #define fwrite freopen("output.txt","w",stdout)
- #define inf (1e18)
- #define chng(a,b) a^=b^=a^=b;
- #define clr(abc,z) memset(abc,z,sizeof(abc))
- #define PI acos(-1)
- #define pi 3.14159265358979323846264338327950288419716939937510
- #define fr(i,a,b) for(i=a;i<=b;i++)
- #define cspf printf("Case %d:", cas++);
- #define csco cout<<"Case "<<cas++<<": ";
- #define mod 1000000007
- #ifdef ENAM
- #define deb(args...) {dbg,args; cerr<<endl;}
- #else
- #define deb(args...)
- #endif
- using namespace std;
- struct _deb{
- template<typename T> _deb& operator , (const T& _temp){
- cerr<<_temp<<" ";
- return *this;
- }
- }dbg;
- /// debug template credit: Bidhan Roy
- ll bigmod(ll sonkha,ll ghat,ll vag_const){ll vag_shesh=1;while(ghat>0){if(ghat%2==1){vag_shesh=(vag_shesh*sonkha)%vag_const;}ghat/=2;sonkha=(sonkha*sonkha)%vag_const;}return vag_shesh;}
- ll inverse_mod(ll bivajok, ll vag_const){return bigmod(bivajok,vag_const-2, vag_const);}
- int par[sz];
- priority_queue< pair<int, pair<int,int> > ,
- vector< pair<int, pair<int,int> > >,
- greater< pair<int,pair<int,int> > > >pq;
- int find_set(int node)
- {
- if(par[node] == node)
- return node;
- return par[node] = find_set(par[node]);
- }
- int kruskal()
- {
- vector < pair<int, pair<int,int> > > ans;
- int c, u, v,tot=0,x,y;
- while(!pq.empty())
- {
- c = pq.top().first;
- u = pq.top().second.first;
- v = pq.top().second.second;
- x = find_set(u);
- y = find_set(v);
- if(x!=y)
- {
- ans.pb({c, {u,v} });
- par[x] = y;
- tot+=c;
- }
- pq.pop();
- }
- for (int i = 0; i<ans.size(); i++)
- {
- cout<<i<<":"<<ans[i].first<<" -> ("
- <<ans[i].second.first << "," <<
- ans[i].second.second << ")\n";
- }
- return tot;
- }
- int main()
- {
- #ifdef ENAM
- // fread;
- // fwrite;
- #endif // ENAM
- _
- int cas = 1,t,n,m,x,y,z;
- // clock_t begin, end;
- // double time_spent;
- // begin = clock();
- cin>>n>>m;
- for (int i = 0; i<=n; i++)
- par[i]=i;
- for (int i = 0; i<m; i++)
- {
- cin>>x>>y>>z;
- pq.push({z,{x,y}});
- }
- cout<<"Total Cost of MST = "<<kruskal()<<"\n";
- // end = clock();
- // time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
- // cerr<<"Time spent = "<<time_spent<<endl;
- return 0;
- }
- /**
- 6 8
- 1 2 1
- 1 3 1
- 1 5 1
- 2 4 3
- 2 5 2
- 3 6 2
- 4 6 3
- 5 6 5
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement