首页 > 代码库 > HDU2586
HDU2586
一道多次询问的最近公共祖先问题。
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 40000 + 10; struct Edge{ int to,cost; Edge(){}; Edge(int _to,int _cost) :to(_to),cost(_cost){}; }; vector<Edge> tree[MAXN]; vector<Edge> Qes[MAXN]; int degree[MAXN]; int f[MAXN]; bool vst[MAXN]; int dist[MAXN]; int ancestor[MAXN]; int ans[MAXN]; int rank[MAXN]; int N,M; void init(){ for(int i = 0;i <= N;++i){ degree[i] = 0; f[i] = i; ans[i] = -1; rank[i] = 0; dist[i] = 0; vst[i] = false; ancestor[i] = -1; tree[i].clear(); Qes[i].clear(); } } int Find(int x){ if(x == f[x]) return x; return f[x] = Find(f[x]); } void LCA(int u){ int sz = tree[u].size(); for(int i = 0;i < sz;++i){ Edge& e = tree[u][i]; if(!vst[e.to]){ vst[e.to] = 1; dist[e.to] = dist[u] + e.cost; LCA(e.to); f[e.to] = u; int k = Qes[e.to].size(); for(int j = 0;j < k;++j){ Edge& et = Qes[e.to][j]; if(vst[et.to]&&ans[et.cost] == -1){ //还未遍历到 if(et.to == e.to) ans[et.cost] = 0; else ans[et.cost] = dist[e.to] + dist[et.to] - 2*dist[Find(et.to)]; } } } } } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d%d",&N,&M); init(); int x,y,c; for(int i = 1;i < N;++i){ scanf("%d%d%d",&x,&y,&c); tree[x].push_back(Edge(y,c)); tree[y].push_back(Edge(x,c)); } for(int i = 0;i < M;++i){ scanf("%d%d",&x,&y); Qes[x].push_back(Edge(y,i)); Qes[y].push_back(Edge(x,i)); } vst[1] = 1; LCA(1); for(int i = 0;i < M;++i){ printf("%d\n",ans[i]); } } return 0; }
HDU2586
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。