Advertisement
aimon1337

Untitled

May 26th, 2020
341
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. //#include <cstring>
  4. //#include <cmath>
  5. #include <algorithm>
  6. using namespace std;
  7. ifstream fin("date.in");
  8. //ofstream fout("date.out");
  9. const int mxn=1e3;
  10. const int nax=1e5;
  11. struct muchie{
  12.     int x,y;
  13.     int c;
  14. }v[nax];
  15. int L[nax], n, m;
  16. bool comparare(muchie a, muchie b){
  17.     return a.c < b.c;
  18. }
  19. int main(){
  20.     int i, j;
  21.     int ax,ay;
  22.     fin>>n>>m;
  23.     for(i=1;i<=m;++i){
  24.         fin>>v[i].x>>v[i].y>>v[i].c;
  25.     }
  26.     sort(v, v+m, comparare);
  27.     for(i=1;i<=n;++i)
  28.         L[i]=i;
  29.     int ct=0, k=0;
  30.     for(i=1;i<=n && k<n; ++i){
  31.         if(L[v[i].x] != L[v[i].y]){
  32.             ct+=v[i].c;
  33.             ax=L[v[i].x]; ay=L[v[i].y];
  34.             for(j=1;j<=n;++j)
  35.                 if(L[j]==ay)
  36.                     L[j]=ax;
  37.         }
  38.     }
  39.     cout<<ct<<"\n";
  40.     cout<<endl; return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement