題目大意: 給你一個n個節點m條邊的森林，再給定q個查詢，每次查詢森林裡兩個點的最近距離。n ,m <= 10000,q <= 100萬
解題思路：十分經典的LCA,其實也是十分樸素的LCA題，只不過這題給定的是森林而不是一棵樹，差別就只是一個for循環用來多次計算。看到一篇aiguoruan的博客，講lca講得較易懂，引用下：tarjan 求解lca主要利用並查集的想法：首先遍歷樹，從葉子節點開始向上合並成一棵棵的子樹，然後子樹並子樹，就成了一棵樹了。查找是在合並的時候進行的，exp：u是s,t的lca，先從u節點進入s，把s並到u下面，然後發現t沒有被訪問，退到u，再進入t，同樣把t並到u下面，發現s被訪問過了，那麼s的lca也就是s,t的lca了，也就是並差集裡的f[s]。當然，f[s]會變的：假設當前f[s] = u; f[u] = u; 當u並到v的時候，也就是f[u]=v; 相應的f[s] = v。這也就是tarjan求解lca的關鍵方法。
測試數據：
5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5
C艹代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MIN 11000
#define MAX 1100000
struct node {
int v,len;
}cur;
int dist[MIN],visit[MIN]; //dist[i]表示i到根節點的距離，visit[i]判斷是否遍歷過
int n,m,q,ans[MAX],fa[MIN]; //ans[i]記錄第i組查詢應該輸出什麼
vector<node> tree[MIN],query[MIN];//tree記錄森林，query記錄查詢
void Initial() {
memset(dist,0,sizeof(dist));
memset(visit,0,sizeof(visit));
for (int i = 0; i <= n; ++i)
fa[i] = i,tree[i].clear(),query[i].clear();
}
void AddEdge(int a,int b,int c,int kind) {
if (kind == 0) {
//建樹
cur.v = b,cur.len = c;
tree[a].push_back(cur);
}
else {
//離線查詢序列
cur.v = b,cur.len = c;
query[a].push_back(cur);
}
}
int Find(int n) {
//並查集找父節點，並進行路徑壓縮
int x = n,r;
while (fa[x] != x) x = fa[x];
while (n != x) {
r = fa[n];
fa[n] = x,n = r;
}
return x;
}
void Tarjan(int now,int dis,int root) {
fa[now] = now;
dist[now] = dis;
visit[now] = root;
node fuck;
int size = tree[now].size();
for (int i = 0; i < size; ++i) {
fuck = tree[now][i];
if (!visit[fuck.v]) {
Tarjan(fuck.v,dis+fuck.len,root);
fa[fuck.v] = now;
}
}
size = query[now].size();
for (int i = 0; i < size; ++i){
fuck = query[now][i];
if (visit[fuck.v]) { //a->b,b如果未遍歷，那麼b->a的時候還可以計算
if (visit[fuck.v] != root) ans[fuck.len] = -1; //在不同分支中
else ans[fuck.len] = dist[now] + dist[fuck.v] - 2 * dist[Find(fuck.v)];
}
}
}
int main()
{
int i,j,k;
int ta,tb,a,b,c;
while (scanf("%d%d%d",&n,&m,&q) != EOF) {
Initial();
for (i = 1; i <= m; ++i) {
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c,0);
AddEdge(b,a,c,0);
}
for (i = 1; i <= q; ++i) {
scanf("%d%d",&a,&b);
AddEdge(a,b,i,1); //加進vector離線查詢用
AddEdge(b,a,i,1);
}
//Tarjan求解
for (i = 1; i <= n; ++i)
if (!visit[i]) Tarjan(i,0,i); //以i為根遍歷整棵樹
for (i = 1; i <= q; ++i) www.2cto.com
if (ans[i] != -1) printf("%d\n",ans[i]);
else printf("Not connected\n");
}
}
