Source code for submission s645

spider.cpp

  1. #include<iostream>
  2.  
  3. #include<vector>
  4. #include<algorithm>
  5. #include<map>
  6. #include<set>
  7. #include<list>
  8. #include<stack>
  9. #include<queue>
  10.  
  11. #include<stdio.h>
  12. #include<stdlib.h>
  13. #include<math.h>
  14. #include<string.h>
  15.  
  16. using namespace std;
  17.  
  18. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  19.  
  20. #define PB push_back
  21. #define PII pair<int,int>
  22. #define PLL pair<ll,ll>
  23. #define MP make_pair
  24. #define fi first
  25. #define se second
  26.  
  27. #define SIZE(s) (int) (s).size()
  28.  
  29. #define INF 987654321
  30. #define ll long long
  31.  
  32. //----------------------
  33.  
  34. #define MAX 2047
  35.  
  36. int N, M;
  37.  
  38. int dad[MAX];
  39.  
  40. void make_set(int x)
  41. {
  42. dad[x] = -1;
  43. }
  44.  
  45. int find_set(int x)
  46. {
  47. int k,i=x;
  48. while(dad[i]>=0)
  49. i = dad[i];
  50. while(dad[x]>=0)
  51. {
  52. k=dad[x];
  53. dad[x]=i;
  54. x=k;
  55. }
  56. return x;
  57. }
  58.  
  59. void union_set(int x, int y)
  60. {
  61. int sx=find_set(x), sy=find_set(y);
  62. if (sx!=sy)
  63. {
  64. if (dad[sx]<dad[sy])
  65. {
  66. dad[sx]+=dad[sy];
  67. dad[sy]=sx;
  68. }
  69. else
  70. {
  71. dad[sy]+=dad[sx];
  72. dad[sx]=sy;
  73. }
  74. }
  75. }
  76.  
  77.  
  78. bool discon()
  79. {
  80. int root = find_set(0);
  81. FOR(i,1,N-1)
  82. if (find_set(i) != root)
  83. return true;
  84. return false;
  85. }
  86.  
  87.  
  88. vector< pair<int, PII> > hrany;
  89.  
  90. int main()
  91. {
  92. int a, b, d, max_a=-1, max_b=-1, max_d;
  93.  
  94. while(scanf("%d %d",&N,&M)==2)
  95. {
  96. hrany.clear();
  97. max_d = -1;
  98. FOR(i,0,M-1)
  99. {
  100. scanf("%d %d %d",&a,&b,&d);
  101. a--; b--;
  102. hrany.PB( MP(d, MP(a,b)) );
  103.  
  104. if (d > max_d)
  105. {
  106. max_d = d;
  107. max_a = a;
  108. max_b = b;
  109. }
  110. }
  111.  
  112. sort(hrany.begin(),hrany.end());
  113.  
  114. /*
  115. FOR(i,0,M-1)
  116. {
  117. cout << hrany[i].fi << " " << hrany[i].se.fi << " " << hrany[i].se.se << endl;
  118. }
  119. */
  120.  
  121. FOR(i,0,N-1)
  122. make_set(i);
  123.  
  124. union_set(max_a, max_b);
  125. int sum = -max_d;
  126.  
  127.  
  128. FOR(i,0,M-1)
  129. {
  130. pair< int, PII > h = hrany[i];
  131. if (find_set(h.se.fi) != find_set(h.se.se))
  132. {
  133. union_set(h.se.fi, h.se.se);
  134. sum+= h.fi;
  135. }
  136. }
  137.  
  138. if (discon())
  139. printf("disconnected\n");
  140. else
  141. printf("%d\n",sum);
  142. }
  143.  
  144. return 0;
  145. }
  146.  
  147.