Go to diff to previous submission
#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 22222 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][22], m[MAX][22], depth[MAX]; void dfs(int v, int father, int d){ depth[v] = d; l[v][0] = father; REP(i, 19) l[v][i+1] = l[l[v][i]][i]; REP(i, 19) m[v][i+1] = min(m[v][i], m[l[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; }
--- c4.s1334.cteam002.spider.cpp.0.spider.cpp +++ c4.s1377.cteam002.spider.cpp.0.spider.cpp @@ -66,8 +66,8 @@ } -int l[MAX][20], m[MAX][20], depth[MAX]; +int l[MAX][22], m[MAX][22], depth[MAX]; void dfs(int v, int father, int d){ - l[v][0] = father; depth[v] = d; + l[v][0] = father; REP(i, 19) l[v][i+1] = l[l[v][i]][i]; REP(i, 19) m[v][i+1] = min(m[v][i], m[l[v][i]][i]);