首页 > 代码库 > Hdu 2874(LCA)
Hdu 2874(LCA)
题目链接
Connections between cities
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5037 Accepted Submission(s): 1399Problem DescriptionAfter World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, there might be no path between two cities, no circle exists as well.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.
InputInput consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.
OutputFor each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.
Sample Input5 3 21 3 22 4 35 2 31 44 5
Sample OutputNot connected6HintHintHuge input, scanf recommended.
给出一个森林,然后有Q组询问,每次询问给出u,v,问u和v是否连通?如果连通则输出u到v的最短距离。
由于给出的 并不是一棵树,所以可以加个根节点,但是开始的时候我是从0出发到每个结点都加了一条边,结果TLE.
后来加了并查集,然后从0出发到每个连通分量只加一条边。。轻松水过。
Accepted Code:
1 /************************************************************************* 2 > File Name: 2874.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年09月24日 星期三 20时14分04秒 6 > Propose: 7 ************************************************************************/ 8 #include <cmath> 9 #include <string> 10 #include <cstdio> 11 #include <vector> 12 #include <fstream> 13 #include <cstring> 14 #include <iostream> 15 #include <algorithm> 16 using namespace std; 17 /*Let‘s fight!!!*/ 18 19 const int MAX_N = 10050; 20 const int MAX_LOG = 15; 21 typedef pair<int, int> pii; 22 int N, M, Q; 23 int p[MAX_N][MAX_LOG], depth[MAX_N], Dist[MAX_N], fa[MAX_N]; 24 vector<pii> G[MAX_N]; 25 26 void dfs(int u, int fa, int d, int cost) { 27 p[u][0] = fa; 28 depth[u] = d; 29 Dist[u] = Dist[fa] + cost; 30 for (int i = 0; i < G[u].size(); i++) { 31 int v = G[u][i].first; 32 if (v != fa) dfs(v, u, d + 1, G[u][i].second); 33 } 34 } 35 36 void init() { 37 dfs(0, -1, 0, 0); 38 39 for (int k = 0; k + 1 < MAX_LOG; k++) { 40 for (int v = 0; v <= N; v++) { 41 if (p[v][k] < 0) p[v][k + 1] = -1; 42 else p[v][k + 1] = p[p[v][k]][k]; 43 } 44 } 45 } 46 47 int lca(int u, int v) { 48 if (depth[u] > depth[v]) swap(u, v); 49 for (int k = 0; k < MAX_LOG; k++) { 50 if ((depth[v] - depth[u]) >> k & 1) { 51 v = p[v][k]; 52 } 53 } 54 if (u == v) return u; 55 for (int k = MAX_LOG - 1; k >= 0; k--) { 56 if (p[u][k] != p[v][k]) { 57 u = p[u][k]; 58 v = p[v][k]; 59 } 60 } 61 return p[u][0]; 62 } 68 69 int findfa(int x) { 70 return x != fa[x] ? fa[x] = findfa(fa[x]) : x; 71 } 72 73 void read(int &res) { 74 res = 0; 75 char c = ‘ ‘; 76 while (c < ‘0‘ || c > ‘9‘) c = getchar(); 77 while (c >= ‘0‘ && c <= ‘9‘) res = res * 10 + c - ‘0‘, c = getchar(); 78 } 79 80 int main(void) { 81 while (~scanf("%d %d %d", &N, &M, &Q)) { 82 for (int i = 0; i <= N; i++) G[i].clear(), fa[i] = i; 83 84 for (int i = 1; i <= M; i++) { 85 int u, v, w; 86 read(u), read(v), read(w); 87 //scanf("%d %d %d", &u, &v, &w); 88 G[u].push_back(pii(v, w)); 89 G[v].push_back(pii(u, w)); 90 int x = findfa(u), y = findfa(v); 91 if (x != y) { 92 fa[y] = x; 93 } 94 } 95 for (int i = 1; i <= N; i++) if (fa[i] == i) { 96 G[0].push_back(pii(i, 0)); 97 G[i].push_back(pii(0, 0)); 98 } 99 init();100 101 while (Q--) {102 int u, v;103 read(u), read(v);104 //scanf("%d %d", &u, &v);105 int x = lca(u, v);106 if (x == 0) puts("Not connected"); 107 else printf("%d\n", Dist[u] + Dist[v] - 2 * Dist[x]);108 }109 }110 return 0;111 }
Hdu 2874(LCA)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。