Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define mp make_pair
- #define pb push_back
- #define INF 0x3f3f3f3f
- #define LINF 0x3f3f3f3f3f3f3f3fLL
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef set<int> si;
- typedef pair<int,int> ii;
- typedef vector<ii> vii;
- typedef map<string,int> msi;
- typedef map<int,int> mi;
- class UnionFind{
- public:
- vector<int>p,rank;
- UnionFind(int n){
- p.resize(n);
- rank.assign(n,0);
- for(int i=0;i<n;i++){
- p[i]=i;
- }
- }
- int findSet(int i){
- if(p[i] == i) return i;
- return (p[i] = findSet(p[i]));
- }
- bool isSameSet(int i,int j){
- return findSet(i) == findSet(j);
- }
- void unionSet(int i, int j){
- if(isSameSet(i,j)) return;
- int x = findSet(i);
- int y = findSet(j);
- if(rank[x] > rank[y]){
- p[y] = x;
- return;
- }
- p[x] = y;
- if(rank[x] == rank[y]) rank[y]++;
- }
- };
- struct aresta
- {
- int a,b,c;
- aresta(int x,int y,int z){
- a = x;
- b = y;
- c = z;
- }
- bool operator<(const aresta o) const{
- return c < o.c;
- }
- };
- int main(){
- int n,m;
- while(cin >>n>>m){
- UnionFind uf(n+1);
- vector<aresta> ar;
- for(int i =0 ; i<m;i++){
- int a,b,c;
- cin >> a>>b>>c;
- ar.pb(aresta(a,b,c));
- }
- sort(ar.begin(),ar.end());
- ll custo =0;
- for(int i=0;i<m;i++){
- if(!uf.isSameSet(ar[i].a,ar[i].b)){
- uf.unionSet(ar[i].a,ar[i].b);
- custo += ar[i].c;
- }
- }
- map<int,int> cont;
- for(int i=1;i<=n;i++){
- cont[uf.findSet(i)]++;
- }
- if(cont.size()>1) cout << "impossivel\n";
- else cout << custo<<'\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement