设为首页 加入收藏

TOP

HDU 2586 How Far Away？（Tarjan离线算法求lca）
2015-11-21 00:56:13 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 2586 How Far Away Tarjan 算法 lca

题意：给定一棵树n个节点m个询问，每次询问两个节点之间的距离。

思路：Tarjan离线算法求lca。

这题一开始交了n发一直爆栈.......百度了一下大概说的是这样hdu用的是windows服务器所以栈大小极其坑爹,稍微深一点的递归就会爆栈（正式比赛一般不会爆）

解决方法就是加一句#pragma comment(linker, /STACK:1024000000,1024000000) 用c++交就好.....当然这只是针对比较坑爹oj来说的取巧的方法

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long using namespace std; #pragma comment(linker, /STACK:1024000000,1024000000) const int maxn = 50000; //const int INF = 0x3f3f3f3f; int dist[maxn], pnt[maxn], ans[maxn]; bool vis[maxn]; vector
               
                 G[maxn], w[maxn], query[maxn], num[maxn]; int n, m; int find(int x) { if(x == pnt[x]) return x; return pnt[x] = find(pnt[x]); } void dfs(int u, int val) { dist[u] = val; vis[u] = 1; pnt[u] = u; int sz1 = G[u].size(); for(int i = 0; i < sz1; i++) { int v = G[u][i]; if(vis[v]) continue; dfs(v, val+w[u][i]); pnt[v] = u; } int sz2 = query[u].size(); for(int i = 0; i < sz2; i++) { int v = query[u][i]; if(vis[v]) ans[num[u][i]] = dist[u] + dist[v] - 2*dist[find(v)]; } } void init() { memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) { G[i].clear(); w[i].clear(); query[i].clear(); num[i].clear(); } } int main() { // freopen(input.txt, r, stdin); int T; cin >> T; while(T--) { cin >> n >> m; init(); for(int i = 0; i < n-1; i++) { int u, v, d; scanf(%d%d%d, &u, &v, &d); G[u].push_back(v); G[v].push_back(u); w[u].push_back(d); w[v].push_back(d); } for(int i = 0; i < m; i++) { int u, v; scanf(%d%d, &u, &v); query[u].push_back(v); query[v].push_back(u); num[u].push_back(i); num[v].push_back(i); } dfs(1, 0); for(int i = 0; i < m; i++) printf(%d , ans[i]); } return 0; }
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：POJ 题目2245 Lotto（DFS水） 下一篇：hdu2489Minimal Ratio Tree 最小..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: