Source code for submission s587

spider.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. ///////////////////////////////////////////////////////////////////////////
  29.  
  30. const int MAX = 2007;
  31. int N, M;
  32. int parent[MAX];
  33.  
  34. int get(int n)
  35. {
  36. return parent[n] = (n == parent[n] ? n : get(parent[n]));
  37. }
  38.  
  39. bool joined(int a, int b)
  40. {
  41. a = get(a);
  42. b = get(b);
  43. return a == b;
  44. }
  45.  
  46. void join(int a, int b)
  47. {
  48. a = get(a);
  49. b = get(b);
  50. parent[a] = b;
  51. }
  52.  
  53. struct Edge
  54. {
  55. int a, b, c;
  56. bool operator<(const Edge & e) const { return c < e.c; }
  57. } edges[1000000];
  58.  
  59. int main()
  60. {
  61. while (scanf("%d%d", &N, &M) == 2)
  62. {
  63. REP(i, N) parent[i] = i;
  64. REP(i, M)
  65. {
  66. scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c);
  67. --edges[i].a;
  68. --edges[i].b;
  69. }
  70. sort(edges, edges+M);
  71.  
  72. int used = 0, result = 0;
  73. if (M)
  74. {
  75. result -= edges[M-1].c;
  76. join(edges[M-1].a, edges[M-1].b);
  77. ++used;
  78. }
  79. REP(i, M-1)
  80. {
  81. if (!joined(edges[i].a, edges[i].b))
  82. {
  83. join(edges[i].a, edges[i].b);
  84. result += edges[i].c;
  85. ++used;
  86. }
  87. }
  88.  
  89. if (used != N-1)
  90. printf("disconnected\n");
  91. else
  92. printf("%d\n", result);
  93. }
  94. return 0;
  95. }
  96.