切换到宽版
  • 12328阅读
  • 1回复

LCA问题@POJ [复制链接]

上一主题 下一主题
离线topten
 

只看楼主 倒序阅读 0 发表于: 2007-10-24
今天遇到了一个LCA问题:
http://acm.pku.cn/JudgeOnline/problem?id=1986

写出了代码,是用Tarjan离线算法写的
却Runtime Error
不知道,有没有更好的方法。
有的话请跟我联系:QQ:80424704
from:Acmer@dlut
(代码如下)

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
const long max = 1000;
struct Node{int v,d;Node *next;Node(){next=NULL;}}*node[max],*ptr[max];
int fa[max];

bool black[max];
int net[max][max],n1;
using namespace std;
int findset(int v)
{
    int t,j;
    j=t=v;
    while(fa[t]!=t)
    {
        t=fa[t];
    }
    while(fa[v]!=v)
    {
    //    dis[v][fa[v]]=dis[fa[v]][v]=
        j=fa[v];
        fa[v]=t;
        v=j;
    }
    return t;
}
/*void unionset(long a,long b)
{
    a=findset(a);
    b=findset(b);
    if(rank[a]>rank)
    {
        fa=a;
    }
    else
    {
        fa[a]=b;
        if(rank[a]==rank)rank++;
    }
}*/
void lca(int u)
{
    Node *p=node;
    p=p->next;
    fa=u;
    black=1;
    while(p)
    {
        if(!black[p->v])
        {
            lca(p->v);
            fa[findset(p->v)]=u;
        }
        p=p->next;
    }
    p=node->next;
/*    while(p)
    {
        if(black[p->v])
        {
            net[p->v]=net[p->v]=fa[findset(p->v)];
        }
        p=p->next;
    }*/
    for(int i=0;i<n1;i++)
    {
        if(black)
        {
            net=net=fa[findset(i)];
        }
    }
   
}
bool ok=0;
long sum=0;
void dfs(int a,int b,int ans)
{
    Node *p=node[a];
    if(p->v==b){sum+=ans;ok=1;return ;}
    p=p->next;
    while(p)
    {
        if(ok)return;
        dfs(p->v,b,ans+p->d);
        p=p->next;
    }
}
int main()
{
    long m , n , i, j , k;
    while(scanf("%ld%ld",&m,&n)!=EOF)
    {
        n1=m;
        long a, b,c;
        for(i=0;i<m;i++)
        {
            node=new Node;
            ptr=node;
            node->v=i;
            black=0;fa=i;
        //    rank=0;
        }
        for(i=0;i<n;i++)
        {
           
            char s[10];
            scanf("%ld%ld%ld%s",&a,&b,&c,s);
            a--;b--;
            ptr[a]->next=new Node;
            ptr[a]=ptr[a]->next;
            ptr[a]->v=b;
            ptr[a]->d=c;
            ptr->next=new Node;
            ptr=ptr->next;
            ptr->v=a;
            ptr->d=c;
        }
        lca(0);
        scanf("%ld",&a);
        for(i=0;i<a;i++)
        {
            scanf("%ld%ld",&b,&c);
            b--;c--;
            sum=0;
        //    printf("%ld\n",net[c]);
            ok=0;
            dfs(b,net[c],0);
            ok=0;
            dfs(c,net[c],0);
            printf("%ld\n",sum);
        }
    }
    return 0;
}
离线yonghu86cs
只看该作者 1 发表于: 2008-02-23
...
快速回复
限100 字节
 
上一个 下一个