题目链接【https://vjudge.net/problem/HDU-2874】
题意： 输入一个森林，总节点不超过N(N<10000),由C次询问（C<1000000）,每次询问两个点，如果来联通输出，两点之间的距离，如果不来联通，输出“Not connected”;
思路：首先判断u,v两个点在不在同一个树上，用并查集来做，如果在，就求两者的LCA，输入距离dis[u->v]=dis[u]+dis[v]-2*dis[LCA(u,v)]。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 10050; int N, M, C; struct node { int id, next, len; } E[maxn << 1]; int head[maxn << 1], num; void initlist() { memset(head, -1, sizeof(head)); num = 0; } void adde(int u, int v, int len) { E[num].id = u; E[num].len = len; E[num].next = head[v]; head[v] = num++; } //----------------------------------------邻接表 int fa[maxn<<1]; void initfa() { for(int i = 0; i <= N; i++) fa[i] = i; } int Find(int id) { if(id == fa[id]) return id; else return fa[id] = Find(fa[id]); } void addu(int u, int v) { int x = Find(u); int y = Find(v); if(x != y) fa[x] = y; } //----------------------------------------并查集 int p[16][maxn], dep[maxn], dis[maxn], vis[maxn]; void DFS(int u, int FA) { vis[u] = 1; for(int l = head[u]; l != -1; l = E[l].next) { int id = E[l].id; if(id == FA||vis[id]) continue; dep[id] = dep[u] + 1; dis[id] = dis[u] + E[l].len; p[0][id] = u; DFS(id, u); } } void initlca() { memset(p, -1, sizeof(p)); memset(dep,0,sizeof(dep)); memset(dis, 0, sizeof(dis)); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= N; i++) { if(!vis[i]) DFS(i, -1); } for(int k = 0; k + 1 <= 15; k++) for(int u = 1; u <= N; u++) { if(p[k][u] < 0) p[k + 1][u] = -1; else p[k + 1][u] = p[k][p[k][u]]; } } int LCA(int u, int v) { if(dep[u] > dep[v]) swap(u, v); for(int k = 0; k <= 15; k++) { if((dep[v] - dep[u]) >> k & 1) v = p[k][v]; } if(u == v) return u; for(int k = 15; k >= 0; k--) { if(p[k][u] != p[k][v]) { u = p[k][u]; v = p[k][v]; } } return p[0][u]; } //----------------------------------------LCA int main () { while(~scanf("%d%d%d", &N, &M, &C)) { initlist(); initfa(); int u, v, ds; for(int i = 1; i <= M; i++) { scanf("%d%d%d", &u, &v, &ds); adde(u, v, ds); adde(v, u, ds); addu(u, v); } initlca(); for(int i=1;i<=C;i++) { scanf("%d%d",&u,&v); int x=Find(u); int y=Find(v); if(x==y) { printf("%d ",dis[u]+dis[v]-2*dis[LCA(u,v)]); } else printf("Not connected "); } } return 0; }
//#include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 100050; //---------------------------------//邻接表 struct node { int to, len, next; } E[MAXN * 2]; int p[MAXN * 2], tot; void init() { memset(p, -1, sizeof(p)); tot = 0; } void add(int u, int v, int len) { E[tot].to = v; E[tot].len = len; E[tot].next = p[u]; p[u] = tot++; } //---------------------------------//并查集 int fa[MAXN * 2]; void init2(int n) { for(int i = 1; i <= n; i++) fa[i] = i; } int Find(int x) { if(x == fa[x]) return fa[x]; else return fa[x] = Find(fa[x]); } void join (int i, int j) { int x = Find(i); int y = Find(j); if(x != y) fa[y] = x; } //----------------------------------//LAC int ver[MAXN * 2], vis[MAXN], fst[MAXN], R[MAXN * 2]; int dis[MAXN], KT[MAXN * 2], dp[MAXN * 2][25]; void init3() { memset(vis, 0, sizeof(vis)); tot = 0; } void DFS(int u, int dep, int len) { vis[u] = 1; ver[++tot] = u; R[tot] = dep; fst[u] = tot; dis[u] = len; for(int k = p[u]; k != -1; k = E[k].next) { int v = E[k].to; if(vis[v]) continue; DFS(v, dep + 1, len + E[k].len); ver[++tot] = u; R[tot] = dep; } } void ST(int n) { KT[1] = 0; for(int i = 2; i <= n; i++) KT[i] = KT[i / 2] + 1; for(int i = 1; i <= n; i++) dp[i][0] = i; for(int j = 1; j <= KT[n]; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++) { int x = dp[i][j - 1]; int y = dp[i + (1 << (j - 1))][j - 1]; dp[i][j] = R[x] < R[y] ? x : y; } } int RMQ(int l, int r) { int k = KT[r - l + 1]; int x = dp[l][k]; int y = dp[r - (1 << k) + 1][k]; return R[x] < R[y] ? x : y; } int LCA(int u, int v) { int l = fst[u], r = fst[v]; if(l > r) swap(l, r); int t = RMQ(l, r); return ver[t]; } //-------------------------------------//主函数 int N, M, C; int main () { while(~scanf("%d%d%d", &N, &M, &C)) { init();// init2(N); int u, v, len; for(int i = 1; i <= M; i++) { scanf("%d%d%d", &u, &v, &len); add(u, v, len); add(v, u, len); join(u, v); } init3(); for(int i = 1; i <= N; i++) { if(vis[i]) continue; DFS(i, 1, 0); } ST(2 * N - 1); for(int i = 1; i <= C; i++) { scanf("%d%d", &u, &v); int x = Find(u); int y = Find(v); if(x != y) { printf("Not connected "); continue; } int lca = LCA(u, v); printf("%d ", dis[u] + dis[v] - 2 * dis[lca]); } } return 0; }