Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define pf(x) printf("%d",x)
- #define pfd(x,y) printf("%d %d",x,y)
- #define pfl(x) printf("%ld",x)
- #define nl printf("\n")
- #define cs(x) printf("Case %d: ",x)
- #define csn(x) printf("Case %d:\n",x)
- #define all(x) x.begin(),x.end()
- #define Find(x,n) find(all(x),n)
- #define pi acos(-1.0)
- #define i64 long long
- #define pb(x) push_back(x)
- #define mset(x,v) memset(x,v,sizeof(x))
- #define sc(n) scanf("%d",&n)
- #define scl(n) scanf("%ld",&n)
- #define scd(n,m) scanf("%d %d",&n,&m)
- #define scdl(n,m) scanf("%ld %ld",&n,&m)
- #define filein freopen("in.txt","r",stdin)
- #define fileout freopen("my.txt","w",stdout)
- #define inf 100000
- #define MAX 10001
- #define MOD 4294967296
- bool isUpper(char ch){ if( ch>='A' && ch<='Z' ) return true; return false; }
- bool isLower(char ch){ if( ch>='a' && ch<='z') return true; return false;}
- bool isLetter(char ch){ if( ch>='A' && ch<='Z' || ch>='a' && ch<='z') return true; return false; }
- bool isDigit(char ch){ if( ch>='0' && ch<='9') return true; return false; }
- char toLower(char ch){ if (isUpper(ch)) return (ch+32); return ch; }
- char toUpper(char ch){ if (isLower(ch)) return (ch-32); return ch; }
- template<class T>bool isEven(T a){ return (a%2==0);}
- template<class T>T sq(T a){ return (a*a); }
- template<class T>T gcd(T a,T b){ return b==0 ? a : gcd(b,a%b); }
- template<class T>T lcm(T a,T b){ return (a/gcd(a,b))*b; }
- template<class T>bool isPrime(T n){ for(T i=2; i*i<=n; i++){ if(n%i==0) return false; } return true; }
- template<class T>T Pow(T n,T p) { T res=n; for(T i=1;i<p; i++){ res *= n; } return res; }
- template<class T>T Max(T n,T p) { if(n>=p) return n; return p; }
- template<class T>T ABS(T n) { return (n<0) ? (-n) : n; }
- struct node
- {
- int u,v;
- i64 w;
- node( int U,int V,i64 W ) { u=U; v=V; w=W; }
- bool operator < ( const node& p )const { return w < p.w;}
- };
- vector<node>g;
- int par[MAX];
- int parent(int x){
- return (par[x]==x) ? x : parent(par[x]);
- }
- i64 mst(int n){
- int sz=g.size();
- int nodes=0;
- i64 res=0;
- for(int i=0;i<sz;i++){
- int u=parent(g[i].u);
- int v=parent(g[i].v);
- if( u!=v ){
- par[u]=v;
- res += g[i].w;
- nodes++;
- if( nodes == n-1 ) return res;
- }
- }
- }
- int main()
- {
- int n,m;
- while( scanf("%d %d",&n,&m) == 2 ){
- for(int i=0;i<m;i++){
- int u,v;
- i64 w;
- scanf("%d %d %lld",&u,&v,&w);
- par[u]=u;
- par[v]=v;
- g.pb( node(u,v,w) );
- }
- sort( all(g) );
- printf("%lld\n",mst(n));
- g.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement