熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> C編程 >> 正文

求任意兩點到最近公共祖先的距離

2013-11-12 23:34:00  來源: C編程 

  虛擬賽的時候一看是求任意兩點的最短路不管怎麼優化都超時最近做一些樹的題目這是求任意兩點到最近公共祖先的距離先用並差集判斷是否聯通聯通就求最近公共祖先先把圖建成一棵棵樹
    #include<stringh>
    #include<stdioh>
    #define N
    int father[N]dfs[N]nvis[N]head[N]numf[N]ansdis[N];
    struct edge
    {
    int stednextw;
    }E[N*];
    void addedge(int xint yint w)
    {
    E[num]st=x;
    E[num]ed=y;
    E[num]w=w;
    E[num]next=head[x];
    head[x]=num++;
    }
    int find(int a)
    {
    if(f[a]!=a)
    f[a]=find(f[a])
    return f[a];
    }
    void dfs(int u)
    {
    int iv;
    vis[u]=;
    for(i=head[u];i!=;i=E[i]next)
    {
    v=E[i]ed;
    if(vis[v]==)continue;
    father[v]=u;
    dfs[v]=dfs[u]+;
    dis[v]=E[i]w;
    dfs(v)
    }
    if(ans<dfs[u])
    ans=dfs[u];
    }
    int LCA(int xint y)
    {
    int sum=;
    while(dfs[x]>dfs[y])
    {
    sum+=dis[x];
    x=father[x];
    }

  while(dfs[y]>dfs[x])
    {
    sum+=dis[y];
    y=father[y];
    }
    while(x!=y)
    {
    sum+=(dis[x]+dis[y])
    x=father[x];
    y=father[y];
    }
    return sum;
    }
    int main()
    {
    int ijkxymansw;
    while(scanf(%d%d%d&n&m&k)!=
    {
    memset(headsizeof(head))
    num=;
    for(i=;i<=n;i++)
    f[i]=i;
    for(i=;i<m;i++)
    {
    scanf(%d%d%d&x&y&w)
    addedge(xyw)
    addedge(yxw)
    x=find(x)
    y=find(y)
    if(x!=y)
    f[x]=find(y)
    }
    memset(vissizeof(vis))
    ans=;
    for(i=;i<=n;i++)
    {
    if(vis[i]==
    {
    dis[i]=;
    dfs[i]=ans;
    father[i]=i;
    dfs(i)
    ans++;
    }
    }
    while(k
    {
    scanf(%d%d&x&y)
    if(find(x)!=find(y))
    {printf(Not connected\ncontinue;}
    j=LCA(xy)
    printf(%d\nj)
    }
    }
    return ;
    }


From:http://tw.wingwit.com/Article/program/c/201311/11104.html
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.