Source code for submission s1360

Go to diff to previous submission

spider.cpp

  1. #include <vector>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <cstdio>
  5. using namespace std;
  6.  
  7. struct edge {
  8. int x, y, w;
  9. edge() {}
  10. edge(int x, int y, int w) : x(x), y(y), w(w) {}
  11. bool operator < (const edge &e) const {
  12. return w < e.w;
  13. }
  14. };
  15.  
  16. vector<int> parent;
  17. void init(int n) {
  18. parent.resize(n);
  19. for (int i = 0; i < n; ++i) {
  20. parent[i] = i;
  21. }
  22. }
  23.  
  24. int find(int i) {
  25. if (parent[i] == i) return i;
  26. parent[i] = find(parent[i]);
  27. return parent[i];
  28. }
  29.  
  30. void merge(int i, int j) {
  31. parent[find(i)] = find(j);
  32. }
  33.  
  34. bool kruskal(vector<edge> &g, vector<edge> &tree, int n) {
  35. init(n);
  36. sort(g.begin(), g.end());
  37. edge e = g.back();
  38. tree.push_back(e);
  39. merge(e.x, e.y);
  40. for(int i = 0; i < (int) g.size(); ++i) {
  41. if (find(g[i].x) != find(g[i].y)) {
  42. merge(g[i].x, g[i].y);
  43. tree.push_back(g[i]);
  44. }
  45. }
  46. return (int) tree.size() == n - 1;
  47. }
  48.  
  49. int bfs(vector<vector<pair<int, int> > > &t, int u, int v) {
  50. vector<bool> mark(t.size(), false);
  51. queue<pair<int, int> > q;
  52. q.push(make_pair(u, 0));
  53. mark[u] = true;
  54. while(not q.empty()) {
  55. int x = q.front().first;
  56. int l = q.front().second;
  57. q.pop();
  58. //printf("%d %d\n", x, l); fflush(stdout);
  59. if (x == v) return l;
  60. for (int i = 0; i < (int) t[x].size(); ++i) {
  61. int y = t[x][i].first;
  62. if (not mark[y]) {
  63. mark[y] = true;
  64. int nl = max(l, t[x][i].second);
  65. q.push(make_pair(y, nl));
  66. }
  67. }
  68. }
  69. return -1;
  70. }
  71.  
  72. int main() {
  73. int n, m;
  74. while(scanf("%d %d", &n, &m) == 2) {
  75. vector<edge> g;
  76. vector<edge> t;
  77. for (int i = 0; i < m; ++i) {
  78. int u,v,l;
  79. scanf("%d %d %d", &u, &v, &l);
  80. --u; --v;
  81. g.push_back(edge(u, v, l));
  82. }
  83. bool connected = kruskal(g, t, n);
  84. int cost = -t[0].w;
  85. for (int i = 1; i < (int) t.size(); ++i)
  86. cost += t[i].w;
  87. if (not connected)
  88. printf("disconnected\n");
  89. else
  90. printf("%d\n", cost);
  91. }
  92. }
  93.  

Diff to submission s1275

spider.cpp

--- c4.s1275.cteam036.spider.cpp.0.spider.cpp
+++ c4.s1360.cteam036.spider.cpp.0.spider.cpp
@@ -32,21 +32,17 @@
 }
 
-edge kruskal(vector<edge> &g, vector<vector<pair<int, int> > > &tree, int n, bool &connected) {
+bool kruskal(vector<edge> &g, vector<edge> &tree, int n) {
         init(n);
-        tree.assign(n, vector<pair<int, int> > ());
         sort(g.begin(), g.end());
-        edge emax(-1, -1, 0);
-        int cnt = 0;
+        edge e = g.back();
+        tree.push_back(e);
+        merge(e.x, e.y);
         for(int i = 0; i < (int) g.size(); ++i) {
                 if (find(g[i].x) != find(g[i].y)) {
                         merge(g[i].x, g[i].y);
-                        tree[g[i].x].push_back(make_pair(g[i].y, g[i].w));
-                        tree[g[i].y].push_back(make_pair(g[i].x, g[i].w));
-                        ++cnt;
-                } else
-                        emax = g[i];
+                        tree.push_back(g[i]);
+                }
         }
-        connected = (cnt == n - 1);
-        return emax;
+        return (int) tree.size() == n - 1;
 }
 
@@ -74,19 +70,9 @@
 }
 
-int sum(vector<vector<pair<int, int> > > &t) {
-        int s = 0;
-        for (int x = 0; x < (int) t.size(); ++x)
-                for (int i = 0; i < (int) t[x].size(); ++i) {
-                        s += t[x][i].second;
-                        //printf("%d %d %d\n", x, t[x][i].first, t[x][i].second);
-                }
-        return s / 2;
-}
-
 int main() {
         int n, m;
         while(scanf("%d %d", &n, &m) == 2) {
                 vector<edge> g;
-                vector<vector<pair<int, int> > > t;
+                vector<edge> t;
                 for (int i = 0; i < m; ++i) {
                         int u,v,l;
@@ -95,11 +81,8 @@
                         g.push_back(edge(u, v, l));
                 }
-                bool connected = true;
-                edge e = kruskal(g, t, n, connected);
-                int cost = sum(t) - e.w;
-                if (e.x < 0)
-                        cost -= e.w;
-                else
-                        cost -= bfs(t, e.x, e.y);
+                bool connected = kruskal(g, t, n);
+                int cost = -t[0].w;
+                for (int i = 1; i < (int) t.size(); ++i)
+                        cost += t[i].w;
                 if (not connected)
                         printf("disconnected\n");