HDU 2874 Connections between cities（LCA离线算法）
最后更新于：2022-04-01 15:52:40
该题用离线算法的时候要注意会MLE， 内存卡的很紧， 所以要想办法优化内存， 利用存储边的数组就行了。
LCA是利用了并查集在树上进行的操作， 由于该题可能不形成一棵树，所以要对所有子树进行LCA。 然后不在一个集合中的两个点不能联通。
下面简单说一下我对LCA的理解： LCA就是dfs+并查集优化。 用dfs深搜， 当其回溯到结点u时， u的子树已经全部搜寻完了， 并且用并查集将其子树合并到了一个集合之中。 这时， 其子树的最近公共祖先就是当前结点u。 当然，其实我们也可以省略掉数组ancestor， 直接将最近公共祖先这个信息维护成并查集的根。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 10000+5;
const int maxq = 1000000+5;
int n,u,m,v,dist[maxn],k,answer[maxq],f[maxn],h[maxn],tt,q,head[maxn],tot;
int _find(int x) { return f[x] == x ? x : f[x] = _find(f[x]); }
void bing(int u, int v) {
int t1 = _find(u);
int t2 = _find(v);
if(t1 != t2) f[t1] = t2;
}
bool vis[maxn];
struct Edge {
int to, next, dist;
}edge[maxn*2];
void addedge(int u, int v, ll dist) {
edge[tot].to = v;
edge[tot].dist = dist;
edge[tot].next = head[u];
head[u] = tot++;
}
struct Query {
int q, next, index;
}query[maxq*2];
void add_query(int u, int v, int index) {
query[tt].q = v;
query[tt].next = h[u];
query[tt].index = index;
h[u] = tt++;
query[tt].q = u;
query[tt].next = h[v];
query[tt].index = index;
h[v] = tt++;
}
void init() {
tot = tt = 0;
for(int i=1;i<=n;i++) {
h[i] = head[i] = -1;
f[i] = i;
vis[i] = false;
}
}
void LCA(int u) {
vis[u] = true;
for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if(vis[v]) continue;
dist[v] = dist[u] + edge[i].dist;
LCA(v);
bing(v, u);
}
for(int i = h[u]; i != -1; i = query[i].next) {
int v = query[i].q;
if(vis[v]) {
answer[query[i].index] = _find(v);
}
}
}
int main() {
while(~scanf("%d%d%d",&n,&m,&q)) {
init();
for(int i=0;i<m;i++) {
scanf("%d%d%d",&u,&v,&k);
addedge(u, v, k);
addedge(v, u, k);
}
for(int i=0;i<q;i++) {
scanf("%d%d",&u,&v);
add_query(u,v,i);
}
for(int i=1;i<=n;i++) {
if(!vis[i]) {
dist[i] = 0;
LCA(i);
}
}
for(int i=0;i<2*q;i+=2) {
u = _find(query[i+1].q); v = _find(query[i].q);
if(u != v) printf("Not connected\n");
else printf("%d\n",dist[query[i+1].q]-dist[answer[i/2]]+dist[query[i].q]-dist[answer[i/2]]);
}
}
return 0;
}
~~~