Advertisement
lmarioza

Untitled

Aug 31st, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define mp make_pair
  5. #define pb push_back
  6. #define INF 0x3f3f3f3f
  7. #define LINF 0x3f3f3f3f3f3f3f3fLL
  8.  
  9. using namespace std;
  10. typedef long long ll;
  11. typedef vector<int> vi;
  12. typedef set<int> si;
  13. typedef pair<int,int> ii;
  14. typedef vector<ii> vii;
  15. typedef map<string,int> msi;
  16. typedef map<int,int> mi;
  17.  
  18. class UnionFind{
  19. public:
  20. vector<int>p,rank;
  21. UnionFind(int n){
  22. p.resize(n);
  23. rank.assign(n,0);
  24. for(int i=0;i<n;i++){
  25. p[i]=i;
  26. }
  27. }
  28. int findSet(int i){
  29. if(p[i] == i) return i;
  30. return (p[i] = findSet(p[i]));
  31. }
  32. bool isSameSet(int i,int j){
  33. return findSet(i) == findSet(j);
  34. }
  35. void unionSet(int i, int j){
  36. if(isSameSet(i,j)) return;
  37. int x = findSet(i);
  38. int y = findSet(j);
  39. if(rank[x] > rank[y]){
  40. p[y] = x;
  41. return;
  42. }
  43. p[x] = y;
  44. if(rank[x] == rank[y]) rank[y]++;
  45. }
  46. };
  47.  
  48. struct aresta
  49. {
  50. int a,b,c;
  51. aresta(int x,int y,int z){
  52. a = x;
  53. b = y;
  54. c = z;
  55. }
  56. bool operator<(const aresta o) const{
  57. return c < o.c;
  58. }
  59. };
  60.  
  61.  
  62. int main(){
  63. int n,m;
  64. while(cin >>n>>m){
  65. UnionFind uf(n+1);
  66. vector<aresta> ar;
  67. for(int i =0 ; i<m;i++){
  68. int a,b,c;
  69. cin >> a>>b>>c;
  70. ar.pb(aresta(a,b,c));
  71. }
  72. sort(ar.begin(),ar.end());
  73. ll custo =0;
  74. for(int i=0;i<m;i++){
  75. if(!uf.isSameSet(ar[i].a,ar[i].b)){
  76. uf.unionSet(ar[i].a,ar[i].b);
  77. custo += ar[i].c;
  78. }
  79. }
  80. map<int,int> cont;
  81. for(int i=1;i<=n;i++){
  82. cont[uf.findSet(i)]++;
  83. }
  84. if(cont.size()>1) cout << "impossivel\n";
  85. else cout << custo<<'\n';
  86. }
  87. return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement