题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2874
题意: 给出 n 个顶点 m 条边的一个森林, 有 k 个形如 x y 的询问, 输出 x, y 之间的最短路径.
思路: 如果将森林换成一棵树的话就是一道 lca 模板题了, 不过本题需要稍作改动.
解法1: tarjan
只需要先判断一下 x, y 是否在一颗树里面就 ok 了, 不过这道题的询问有点多, 很容易 mle.
代码:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 6 const int MAXN = 1e4 + 10; 7 const int MAX = 1e6 + 10; 8 struct node1{ 9 int v, w, next; 10 }edge1[MAXN << 1]; 11 12 struct node2{ 13 int u, v, next; 14 }edge2[MAX << 1];//edge1记录树, edge2记录询问 15 16 int vis[MAXN], pre[MAXN], dis[MAXN], sol[MAX];//vis[i]标记i是否已经搜索过, pre[i]记录i的根节点, dis[i]记录i到根节点的距离 17 int head1[MAXN], head2[MAXN], ip1, ip2, cnt; 18 19 void init(void){ 20 memset(sol, 0, sizeof(sol)); 21 memset(vis, 0, sizeof(vis)); 22 memset(dis, 0, sizeof(dis)); 23 memset(head1, -1, sizeof(head1)); 24 memset(head2, -1, sizeof(head2)); 25 ip1 = ip2 = cnt = 0; 26 } 27 28 void addedge1(int u, int v, int w){//前向星 29 edge1[ip1].v = v; 30 edge1[ip1].w = w; 31 edge1[ip1].next = head1[u]; 32 head1[u] = ip1++; 33 } 34 35 void addedge2(int u, int v){ 36 edge2[ip2].u = u; 37 edge2[ip2].v = v; 38 edge2[ip2].next = head2[u]; 39 head2[u] = ip2++; 40 } 41 42 int find(int x){ 43 return pre[x] == x ? x : pre[x] = find(pre[x]); 44 } 45 46 void jion(int x, int y){ 47 x = find(x); 48 y = find(y); 49 if(x != y) pre[y] = x; 50 } 51 52 void tarjan(int u){ 53 pre[u] = u; 54 vis[u] = cnt;//将不同的联通块标记成不同的数字 55 for(int i = head1[u]; i != -1; i = edge1[i].next){ 56 int v = edge1[i].v; 57 int w = edge1[i].w; 58 if(!vis[v]){ 59 dis[v] = dis[u] + w; 60 tarjan(v); 61 jion(u, v); 62 } 63 } 64 for(int i = head2[u]; i != -1; i = edge2[i].next){ 65 int v = edge2[i].v; 66 if(vis[v] == cnt) sol[i >> 1] = find(v);//只有同一个联通块的顶点才存在lca 67 } 68 } 69 70 int main(void){ 71 int t, n, m, x, y, z; 72 while(~scanf("%d%d%d", &n, &m, &t)){ 73 init(); 74 for(int i = 0; i < m; i++){ 75 scanf("%d%d%d", &x, &y, &z); 76 addedge1(x, y, z); 77 addedge1(y, x, z); 78 } 79 for(int i = 0; i < t; i++){ 80 scanf("%d%d", &x, &y); 81 addedge2(x, y); 82 addedge2(y, x); 83 } 84 for(int i = 1; i <= n; i++){ 85 if(!vis[i]){ 86 cnt++; 87 dis[i] = 0;//顶点到自己的距离为0 88 tarjan(i); 89 } 90 } 91 for(int i = 0; i < t; i++){ 92 int cc = i << 1; 93 int u = edge2[cc].u; 94 int v = edge2[cc].v; 95 int lca = sol[i];//sol开两倍空间会超内存 96 if(!lca) puts("Not connected"); 97 else printf("%d ", dis[u] + dis[v] - 2 * dis[lca]); 98 } 99 } 100 return 0; 101 }
解法2: lca 转 RMQ
可以先拟个虚根, 另外输出前先判一下 x, y 是否在同一棵树里面即可.
代码:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 using namespace std; 6 7 const int inf = 1e9; 8 const int MAXN = 4e4 + 10; 9 struct node{ 10 int v, w, next; 11 }edge[MAXN << 1]; 12 13 int dp[MAXN << 1][30]; //dp[i][j]存储deep数组中下标i开始长度为2^j的子串中最小值的下标 14 int first[MAXN], ver[MAXN << 1], deep[MAXN << 1]; 15 int vis[MAXN], head[MAXN], dis[MAXN], tag[MAXN], ip, indx, cnt; 16 17 inline void init(void){ 18 memset(tag, 0, sizeof(tag)); 19 memset(vis, 0, sizeof(vis)); 20 memset(head, -1, sizeof(head)); 21 ip = 0; 22 indx = 0; 23 cnt = 0; 24 } 25 26 void addedge(int u, int v, int w){ 27 edge[ip].v = v; 28 edge[ip].w = w; 29 edge[ip].next = head[u]; 30 head[u] = ip++; 31 } 32 33 void dfs(int u, int h){ 34 vis[u] = 1; //标记已搜索过的点 35 ver[++indx] = u; //记录dfs路径 36 first[u] = indx; //记录顶点u第一次出现时对应的ver数组的下标 37 deep[indx] = h; //记录ver数组中对应下标的点的深度 38 for(int i = head[u]; i != -1; i = edge[i].next){ 39 int v = edge[i].v; 40 if(!vis[v]){ 41 dis[v] = dis[u] + edge[i].w; 42 dfs(v, h + 1); 43 ver[++indx] = u; 44 deep[indx] = h; 45 } 46 } 47 } 48 49 void dfs1(int u){ 50 tag[u] = cnt; 51 for(int i = head[u]; i != -1; i = edge[i].next){ 52 if(!tag[edge[i].v]) dfs1(edge[i].v); 53 } 54 } 55 56 void ST(int n){ 57 for(int i = 1; i <= n; i++){ 58 dp[i][0] = i; 59 } 60 for(int j = 1; (1 << j) <= n; j++){ 61 for(int i = 1; i + (1 << j) - 1 <= n; i++){ 62 int x = dp[i][j - 1], y = dp[i + (1 << (j - 1))][j - 1]; 63 dp[i][j] = deep[x] < deep[y] ? x : y; 64 } 65 } 66 } 67 68 int RMQ(int l, int r){ 69 int len = log2(r - l + 1); 70 int x = dp[l][len], y = dp[r - (1 << len) + 1][len]; 71 return deep[x] < deep[y] ? x : y; 72 } 73 74 int LCA(int x, int y){ 75 int l = first[x], r = first[y]; 76 if(l > r) swap(l, r); 77 int pos = RMQ(l, r); 78 return ver[pos]; 79 } 80 81 int main(void){ 82 int n, m, k, x, y, z; 83 while(~scanf("%d%d%d", &n, &m, &k)){ 84 init(); 85 for(int i = 0; i < m; i++){ 86 scanf("%d%d%d", &x, &y, &z); 87 addedge(x, y, z); 88 addedge(y, x, z); 89 } 90 for(int i = 1; i <= n; i++){ 91 if(!tag[i]){ 92 cnt++; 93 dfs1(i); 94 addedge(i, 0, inf); //拟个虚根0 95 addedge(0, i, inf); 96 } 97 } 98 dis[0] = 0; 99 dfs(0, 1); 100 ST(2 * n - 1); 101 for(int i = 0; i < k; i++){ 102 scanf("%d%d", &x, &y); 103 int lca = LCA(x, y); 104 if(tag[x] != tag[y]) puts("Not connected"); 105 else printf("%d ", dis[x] + dis[y] - 2 * dis[lca]); 106 } 107 } 108 return 0; 109 }