Source code for submission s1400

Go to diff to previous submission

spider.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. struct edge {
  8. int u, v, l;
  9. bool operator<(const edge & rhs) const
  10. { return l < rhs.l; }
  11. };
  12.  
  13. vector<int> UF;
  14. vector<int> CS;
  15.  
  16. int find_set(int n) {
  17. if (n != UF[n])
  18. UF[n] = find_set(UF[n]);
  19. return UF[n];
  20. }
  21. bool connected(int u, int v)
  22. {
  23. return (find_set(u) == find_set(v));
  24. }
  25. void connect(int u, int v)
  26. {
  27. int uroot = find_set(u);
  28. int vroot = find_set(v);
  29. UF[uroot] = UF[vroot];
  30. }
  31.  
  32. int main()
  33. {
  34. ios_base::sync_with_stdio(false);
  35. int N, M;
  36. while (cin >> N) {
  37. cin >> M;
  38. vector<edge> E (M);
  39.  
  40. // load and sort
  41. for (int i = 0; i < M; ++i) {
  42. edge e;
  43. cin >> e.u >> e.v >> e.l;
  44. E[i] = e;
  45. }
  46. sort (E.begin(), E.end());
  47.  
  48. // UF
  49. UF = vector<int> (N+1);
  50. for (int i = 0; i <= N; ++i)
  51. UF[i] = i;
  52. vector<int> st;
  53. long netl = 0;
  54. int ei = 0; int ec = 0;
  55. while (ei < M && ec < N-2) {
  56. edge e = E[ei];
  57. if (!connected(e.u, e.v)) {
  58. connect(e.u, e.v);
  59. netl += e.l;
  60. ++ec;
  61. st.push_back(ei);
  62. }
  63. ++ei;
  64. }
  65.  
  66. long minnetl = LONG_MAX;
  67. for (int skip = 0; skip < N-1; ++skip) {
  68. netl -= st[skip];
  69. // UF
  70. UF = vector<int> (N+1);
  71. for (int i = 0; i <= N; ++i)
  72. UF[i] = i;
  73. for (int i = 0; i < N-1; ++i)
  74. if (i != skip)
  75. connect(E[st[i]].u, E[st[i]].v);
  76. for (int ei = M-1; ei >= 0; --ei) {
  77. edge e = E[ei];
  78. if (!connected(e.u, e.v)) {
  79. connect(e.u, e.v);
  80. netl -= e.l;
  81. ++ec;
  82. }
  83. }
  84.  
  85. if (ec == N-1)
  86. minnetl = min(minnetl, netl);
  87.  
  88. netl += st[skip];
  89. }
  90.  
  91. if (minnetl < INT_MAX) cout << minnetl << '\n';
  92. else cout << "disconnected\n";
  93. }
  94. return 0;
  95. }
  96.  

Diff to submission s908

spider.cpp

--- c4.s908.cteam012.spider.cpp.0.spider.cpp
+++ c4.s1400.cteam012.spider.cpp.0.spider.cpp
@@ -2,4 +2,5 @@
 #include <vector>
 #include <algorithm>
+#include <climits>
 using namespace std;
 
@@ -22,11 +23,9 @@
         return (find_set(u) == find_set(v));
 }
-int connect(int u, int v)
+void connect(int u, int v)
 {
         int uroot = find_set(u);
         int vroot = find_set(v);
         UF[uroot] = UF[vroot];
-        CS[uroot] = CS[vroot] = CS[uroot] + CS[vroot];
-        return CS[uroot];
 }
 
@@ -38,13 +37,4 @@
                 cin >> M;
                 vector<edge> E (M);
-                UF = vector<int> (N+1);
-                CS = vector<int> (N+1);
-                long netl = 0;
-                
-                // UF
-                for (int i = 0; i <= N; ++i) {
-                        UF[i] = i;
-                        CS[i] = 1;
-                }
 
                 // load and sort
@@ -56,23 +46,49 @@
                 sort (E.begin(), E.end());
 
-                // connect longest
-                edge longest = E.back();
-                netl -= longest.l;
-                connect(longest.u, longest.v);
-                E.pop_back(); --M;
-
-                bool all = false; int ei = 0;
-                while (ei < M && !all) {
+                // UF
+                UF = vector<int> (N+1);
+                for (int i = 0; i <= N; ++i)
+                        UF[i] = i;
+                vector<int> st;
+                long netl = 0;
+                int ei = 0; int ec = 0;
+                while (ei < M  && ec < N-2) {
                         edge e = E[ei];
                         if (!connected(e.u, e.v)) {
-                                if (connect(e.u, e.v) == N)
-                                        all = true;
+                                connect(e.u, e.v);
                                 netl += e.l;
+                                ++ec;
+                                st.push_back(ei);
                         }
                         ++ei;
                 }
 
-                if (all)        cout << netl << '\n';
-                else            cout << "disconnected\n";
+                long minnetl = LONG_MAX;
+                for (int skip = 0; skip < N-1; ++skip) {
+                        netl -= st[skip];
+                        // UF
+                        UF = vector<int> (N+1);
+                        for (int i = 0; i <= N; ++i)
+                                UF[i] = i;
+                        for (int i = 0; i < N-1; ++i)
+                                if (i != skip)
+                                        connect(E[st[i]].u, E[st[i]].v);
+                        for (int ei = M-1; ei >= 0; --ei) {
+                                edge e = E[ei];
+                                if (!connected(e.u, e.v)) {
+                                        connect(e.u, e.v);
+                                        netl -= e.l;
+                                        ++ec;
+                                }
+                        }
+
+                        if (ec == N-1)
+                                minnetl = min(minnetl, netl);
+
+                        netl += st[skip];
+                }
+
+                if (minnetl < INT_MAX)  cout << minnetl << '\n';
+                else                    cout << "disconnected\n";
         }
         return 0;