频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
Hdu 2874 Connections between cities (数据结构_LCA)
2012-07-20 09:19:35      个评论      
收藏   我要投稿

题目大意: 给你一个n个节点m条边的森林,再给定q个查询,每次查询森林里两个点的最近距离。n ,m <= 10000,q <= 100万

解题思路:十分经典的LCA,其实也是十分朴素的LCA题,只不过这题给定的是森林而不是一棵树,差别就只是一个for循环用来多次计算。看到一篇aiguoruan的博客,讲lca讲得较易懂,引用下:tarjan 求解lca主要利用并查集的想法:首先遍历树,从叶子节点开始向上合并成一棵棵的子树,然后子树并子树,就成了一棵树了。查找是在合并的时候进行的,exp:u是s,t的lca,先从u节点进入s,把s并到u下面,然后发现t没有被访问,退到u,再进入t,同样把t并到u下面,发现s被访问过了,那么s的lca也就是s,t的lca了,也就是并差集里的f[s]。当然,f[s]会变的:假设当前f[s] = u; f[u] = u; 当u并到v的时候,也就是f[u]=v; 相应的f[s] = v。这也就是tarjan求解lca的关键方法。

测试数据:
5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5

C艹代码:
[cpp] 
#include <stdio.h> 
#include <string.h> 
#include <vector> 
using namespace std; 
#define MIN 11000 
#define MAX 1100000 
 
 
struct node { 
 
    int v,len; 
}cur; 
int dist[MIN],visit[MIN];         //dist[i]表示i到根节点的距离,visit[i]判断是否遍历过 
int n,m,q,ans[MAX],fa[MIN];       //ans[i]记录第i组查询应该输出什么 
vector<node> tree[MIN],query[MIN];//tree记录森林,query记录查询 
 
 
void Initial() { 
 
    memset(dist,0,sizeof(dist)); 
    memset(visit,0,sizeof(visit)); 
    for (int i = 0; i <= n; ++i) 
        fa[i] = i,tree[i].clear(),query[i].clear(); 

void AddEdge(int a,int b,int c,int kind) { 
 
    if (kind == 0) { 
        //建树 
        cur.v = b,cur.len = c; 
        tree[a].push_back(cur); 
    } 
    else { 
        //离线查询序列 
        cur.v = b,cur.len = c; 
        query[a].push_back(cur); 
    } 

int Find(int n) { 
    //并查集找父节点,并进行路径压缩 
    int x = n,r; 
    while (fa[x] != x) x = fa[x]; 
    while (n != x) { 
 
        r = fa[n]; 
        fa[n] = x,n = r; 
    } 
    return x; 

void Tarjan(int now,int dis,int root) { 
 
    fa[now] = now; 
    dist[now] = dis; 
    visit[now] = root; 
 
 
    node fuck; 
    int size = tree[now].size(); 
    for (int i = 0; i < size; ++i) { 
 
        fuck = tree[now][i]; 
        if (!visit[fuck.v]) { 
          
            Tarjan(fuck.v,dis+fuck.len,root); 
            fa[fuck.v] = now; 
        }  
    } 
 
 
    size = query[now].size(); 
    for (int i = 0; i < size; ++i){ 
 
        fuck = query[now][i]; 
        if (visit[fuck.v]) {                                    //a->b,b如果未遍历,那么b->a的时候还可以计算 
 
            if (visit[fuck.v] != root) ans[fuck.len] = -1;      //在不同分支中 
            else ans[fuck.len] = dist[now] + dist[fuck.v] - 2 * dist[Find(fuck.v)]; 
        } 
    } 

 
 
int main() 

    int i,j,k; 
    int ta,tb,a,b,c; 
 
 
    while (scanf("%d%d%d",&n,&m,&q) != EOF) { 
 
        Initial(); 
        for (i = 1; i <= m; ++i) { 
 
            scanf("%d%d%d",&a,&b,&c); 
            AddEdge(a,b,c,0); 
            AddEdge(b,a,c,0); 
        } 
 
 
        for (i = 1; i <= q; ++i) { 
 
            scanf("%d%d",&a,&b); 
            AddEdge(a,b,i,1);                //加进vector离线查询用 
            AddEdge(b,a,i,1); 
        } 
 
        //Tarjan求解 
        for (i = 1; i <= n; ++i) 
            if (!visit[i]) Tarjan(i,0,i);   //以i为根遍历整棵树 
 
 
        for (i = 1; i <= q; ++i)   www.2cto.com
            if (ans[i] != -1) printf("%d\n",ans[i]); 
            else printf("Not connected\n"); 
    } 


作者:woshi250hua
点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构
上一篇:Poj 2452 Sticks Problem (数据结构_RMQ)
下一篇:C++愤恨者札记1——类对象作为函数参数的数据传递过程
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站