hdu传送门
近似LCA模板题，只不过这里是森林，要用一个并查集判断是否在一棵树上
/* Hdu 2586 LCA */ #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define ms(i,j) memset(i, j, sizeof i); const int MAXN = 10000 + 5, logs = 21; struct edge { int x, y, c; }ed[MAXN*2]; int en; int n, m, c; vector<int> G[MAXN]; int f[MAXN];//并查集, 判断是否在一棵树 int deep[MAXN], pre[MAXN][logs+1], far[MAXN];//lca //并查集 int find(int x) {return f[x]==x ? x : f[x] = find(f[x]);} void merge(int x, int y) {int a = find(x), b = find(y); if (a!=b) f[b] = a;} //LCA void dfs(int x, int p) { pre[x][0] = p; for (int i=1;i<=logs;i++) pre[x][i] = pre[pre[x][i-1]][i-1]; for (int i=0;i<G[x].size();i++) { int v = ed[G[x][i]].y; if (v!=p) { deep[v] = deep[x] + 1; far[v] = far[x] + ed[G[x][i]].c; dfs(v,x); } } } int lca(int a, int b) { if (deep[a]>deep[b]) swap(a,b); for (int i=logs;i>=0;i--) if (deep[pre[b][i]]>=deep[a]) b = pre[b][i]; if (a==b) return a; for (int i=logs;i>=0;i--) if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i]; return pre[a][0]; } void addedge(int x, int y, int v) { en++, ed[en].x = x, ed[en].y = y, ed[en].c = v, G[x].push_back(en); en++, ed[en].x = y, ed[en].y = x, ed[en].c = v, G[y].push_back(en); } void init() { for (int i=1;i<=n;i++) f[i] = i, G[i].clear(); en = 0; for (int i=1;i<=m;i++) { int x, y, k; scanf("%d%d%d", &x, &y, &k); addedge(x,y,k); merge(x, y); } } void solve() { ms(pre, 0); ms(deep, 0); ms(far, 0); for (int i=1;i<=n;i++) if (!deep[i]) { dfs(i, 0); } for (int i=1;i<=c;i++) { int x, y; scanf("%d%d", &x, &y); if (find(x)!=find(y)) printf("Not connected\n"); else printf("%d\n", far[x]+far[y]-2*far[lca(x,y)]); } } int main() { while (scanf("%d%d%d", &n, &m, &c)==3) { init(); solve(); } return 0; }