Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<vector>
- #include<algorithm>
- #define MAXN 200003
- using namespace std;
- struct edge
- {
- long u,v,w;
- bool operator < ( const edge& p ) const
- {
- return w < p.w;
- }
- };
- long pr[MAXN];
- int find(long r)
- {
- if(pr[r]==r)
- return r;
- else
- return pr[r]=find(pr[r]);
- }
- vector<edge>e;
- int mst(long n)
- {
- sort(e.begin(),e.end());
- long count=0,s=0;
- for(long i=0;i<(long)e.size();i++)
- {
- long u=find(e[i].u);
- long v=find(e[i].v);
- if(u!=v)
- {
- pr[u]=v;
- count++;
- s+=e[i].w;
- if(count==n-1)
- break;
- }
- }
- return s;
- }
- int main()
- {
- long n,m,sum;
- while(scanf("%ld%ld",&n,&m)==2)
- {
- if(!n && !m)
- break;
- memset(pr,0,sizeof(pr));
- e.clear();
- sum=0;
- for(long i=0;i<m;i++)
- {
- long u,v,w;
- pr[i]=i;
- scanf("%ld%ld%ld",&u,&v,&w);
- edge get;
- get.u=u; get.v=v; get.w=w;
- sum=sum+w;
- e.push_back(get);
- }
- long save=sum-mst(n);
- printf("%ld\n",save);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement