Source code for submission s1243

Go to diff to previous submission

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.  
  19. using namespace std;
  20. #define DEBUG(x) cerr << ">>> " << #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. #define MAXN 1111111
  31. int N, M;
  32. //vector<int> graph[MAXN], cost[MAXN];
  33. int eA[MAXN], eB[MAXN], eC[MAXN], e[MAXN];
  34.  
  35. int father[MAXN], rank[MAXN];
  36.  
  37. int root(int v){
  38.   if(father[v] == -1) return v;
  39.   return (father[v] = root(father[v]));
  40. }
  41.  
  42. int used;
  43. int DFU(int edge){
  44.   int a = eA[edge], b = eB[edge], c = eC[edge];
  45.   int ca = root(a), cb = root(b);
  46.   //DEBUG(a); DEBUG(b); DEBUG(ca); DEBUG(cb);
  47.   if(ca == cb) return 0;
  48.   if(rank[ca] < rank[cb]) father[ca] = cb;
  49.   else if(rank[ca] > rank[cb]) father[cb] = ca;
  50.   else{
  51.     father[ca] = cb;
  52.     rank[cb]++;
  53.   }
  54.   used++;
  55.   return c;
  56. }
  57.  
  58. bool cmp(int a, int b){
  59.   return eC[a] < eC[b];
  60. }
  61.  
  62. int main() {
  63.   while(scanf("%d%d", &N, &M) != EOF){
  64.     int m = 0;
  65.     REP(i, M){
  66.       int a, b, c;
  67.       scanf("%d%d%d", &a, &b, &c);
  68.       a--; b--;
  69.       eA[i] = a;
  70.       eB[i] = b;
  71.       eC[i] = c;
  72. //      graph[a].push_back(b);
  73. //      graph[b].push_back(a);
  74.  
  75. //      cost[a].push_back(c);
  76. //      cost[b].push_back(c);
  77.       e[i] = i;
  78.       if(eC[m] < eC[i]) m = i;
  79.     }
  80.     REP(i, N){
  81.       father[i] = -1;
  82.       rank[i] = 0;
  83.     }
  84.     eC[m] *= -1;
  85.     sort(e, e + M, cmp);
  86.     int sum = 0;
  87.     used = 0;
  88.     REP(i, M) sum += DFU(e[i]);
  89.     //printf("used: %d\n", used);
  90.     if(used == N-1) printf("%d\n", sum);
  91.     else printf("disconnected\n");
  92.   }
  93.   return 0;
  94. }
  95.  

Diff to submission s1226

spider.cpp

--- c4.s1226.cteam002.spider.cpp.0.spider.cpp
+++ c4.s1243.cteam002.spider.cpp.0.spider.cpp
@@ -44,4 +44,5 @@
   int a = eA[edge], b = eB[edge], c = eC[edge];
   int ca = root(a), cb = root(b);
+  //DEBUG(a); DEBUG(b); DEBUG(ca); DEBUG(cb);
   if(ca == cb) return 0;
   if(rank[ca] < rank[cb]) father[ca] = cb;
@@ -75,7 +76,9 @@
 //      cost[b].push_back(c);
       e[i] = i;
+      if(eC[m] < eC[i]) m = i;
+    }
+    REP(i, N){
       father[i] = -1;
       rank[i] = 0;
-      if(eC[m] < eC[i]) m = i;
     }
     eC[m] *= -1;
@@ -84,4 +87,5 @@
     used = 0;
     REP(i, M) sum += DFU(e[i]);
+    //printf("used: %d\n", used);
     if(used == N-1) printf("%d\n", sum);
     else printf("disconnected\n");