Source: s1324

spider.cpp

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
#define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
 
const int INF = 1<<29;
typedef long long ll;
//////////////////////////////////
 
#define MAXN 1111111
int N, M;
int eA[MAXN], eB[MAXN], eC[MAXN], e[MAXN];
 
int father[MAXN], rank[MAXN];
 
int root(int v){
  if(father[v] == -1) return v;
  return (father[v] = root(father[v]));
}
 
#define MAX 2222
vector<int> graph[MAX], cost[MAX];
 
int T;
int DFU(int edge){
  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;
  else if(rank[ca] > rank[cb]) father[cb] = ca;
  else{
    father[ca] = cb;
    rank[cb]++;
  }
  graph[a].push_back(b);
  graph[b].push_back(a);
  cost[a].push_back(c);
  cost[b].push_back(c);
  T++;
  return c;
}
 
bool cmp(int a, int b){
  return eC[a] < eC[b];
}
 
int l[MAX][20], m[MAX][20], depth[MAX];
void dfs(int v, int father, int d){
  l[v][0] = father;
  depth[v] = d;
  REP(i, 19) l[v][i+1] = l[l[v][i]][i];
  REP(i, 19) m[v][i+1] = min(m[v][i], m[m[v][i]][i]);
  REP(i, graph[v].size()) if(graph[v][i] != father){
    m[graph[v][i]][0] = cost[v][i];
    dfs(graph[v][i], v, d+1);
  }
}
 
int up(int v, int d){
  REP(i, 19) if(d & (1 << i)) v = l[v][i];
  return v;
}
 
int min_up(int v, int d){
  int ans = INF; 
  REP(i, 19) if(d & (1 << i)){ ans = min(ans, m[v][i]); v = l[v][i]; }
  return ans;
}
 
void build_tree(){
  dfs(0, 0, 0);
}
 
int lca(int a, int b){
  FORD(i, 19, 0) if(l[a][i] != l[b][i]){ a = l[a][i]; b = l[b][i]; }
  if(a != b) return l[a][0];
  return a;
}
 
int get(int a, int b){
  if(depth[a] < depth[b]) swap(a, b);
  int ans = min_up(a, depth[a] - depth[b]);
  a = up(a, depth[a] - depth[b]);
  int l = lca(a, b);
  return min(ans, min(min_up(a, depth[a] - depth[l]), min_up(b, depth[b] - depth[l])));
}
 
int main() {
  while(scanf("%d%d", &N, &M) != EOF){
    REP(i, M){
      int a, b, c;
      scanf("%d%d%d", &a, &b, &c);
      a--; b--;
      eA[i] = a;
      eB[i] = b;
      eC[i] = c;
//      graph[a].push_back(b);
//      graph[b].push_back(a);
 
//      cost[a].push_back(c);
//      cost[b].push_back(c);
      e[i] = i;
    }
    REP(i, N){
      father[i] = -1;
      rank[i] = 0;
    }
    sort(e, e + M, cmp);
    int sum = 0;
    T = 0;
    REP(i, M) sum += DFU(e[i]);
    //printf("used: %d\n", used);
    if(T != N-1){ printf("disconnected\n"); continue; }
    build_tree();
    int ans = sum;
    REP(i, M) ans = min(ans, sum - get(eA[i], eB[i]) - eC[i]);
    printf("%d\n", ans);
  }
  return 0;
}

spider.cpp

--- c4.s1243.cteam002.spider.cpp.0.spider.cpp
+++ c4.s1324.cteam002.spider.cpp.0.spider.cpp
@@ -30,5 +30,4 @@
 #define MAXN 1111111
 int N, M;
-//vector<int> graph[MAXN], cost[MAXN];
 int eA[MAXN], eB[MAXN], eC[MAXN], e[MAXN];
 
@@ -40,5 +39,8 @@
 }
 
-int used;
+#define MAX 2222
+vector<int> graph[MAX], cost[MAX];
+
+int T;
 int DFU(int edge){
   int a = eA[edge], b = eB[edge], c = eC[edge];
@@ -52,5 +54,9 @@
     rank[cb]++;
   }
-  used++;
+  graph[a].push_back(b);
+  graph[b].push_back(a);
+  cost[a].push_back(c);
+  cost[b].push_back(c);
+  T++;
   return c;
 }
@@ -60,7 +66,47 @@
 }
 
+int l[MAX][20], m[MAX][20], depth[MAX];
+void dfs(int v, int father, int d){
+  l[v][0] = father;
+  depth[v] = d;
+  REP(i, 19) l[v][i+1] = l[l[v][i]][i];
+  REP(i, 19) m[v][i+1] = min(m[v][i], m[m[v][i]][i]);
+  REP(i, graph[v].size()) if(graph[v][i] != father){
+    m[graph[v][i]][0] = cost[v][i];
+    dfs(graph[v][i], v, d+1);
+  }
+}
+
+int up(int v, int d){
+  REP(i, 19) if(d & (1 << i)) v = l[v][i];
+  return v;
+}
+
+int min_up(int v, int d){
+  int ans = INF; 
+  REP(i, 19) if(d & (1 << i)){ ans = min(ans, m[v][i]); v = l[v][i]; }
+  return ans;
+}
+
+void build_tree(){
+  dfs(0, 0, 0);
+}
+
+int lca(int a, int b){
+  FORD(i, 19, 0) if(l[a][i] != l[b][i]){ a = l[a][i]; b = l[b][i]; }
+  if(a != b) return l[a][0];
+  return a;
+}
+
+int get(int a, int b){
+  if(depth[a] < depth[b]) swap(a, b);
+  int ans = min_up(a, depth[a] - depth[b]);
+  a = up(a, depth[a] - depth[b]);
+  int l = lca(a, b);
+  return min(ans, min(min_up(a, depth[a] - depth[l]), min_up(b, depth[b] - depth[l])));
+}
+
 int main() {
   while(scanf("%d%d", &N, &M) != EOF){
-    int m = 0;
     REP(i, M){
       int a, b, c;
@@ -76,5 +122,4 @@
 //      cost[b].push_back(c);
       e[i] = i;
-      if(eC[m] < eC[i]) m = i;
     }
     REP(i, N){
@@ -82,12 +127,14 @@
       rank[i] = 0;
     }
-    eC[m] *= -1;
     sort(e, e + M, cmp);
     int sum = 0;
-    used = 0;
+    T = 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");
+    if(T != N-1){ printf("disconnected\n"); continue; }
+    build_tree();
+    int ans = sum;
+    REP(i, M) ans = min(ans, sum - get(eA[i], eB[i]) - eC[i]);
+    printf("%d\n", ans);
   }
   return 0;

Source code for submission s1324

spider.cpp

Diff to submission s1243

spider.cpp