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 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; }
--- 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;