poj1986解题报告

题意：还是最近公共祖先

题解：这个题只能用tarjan离线算

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std ;

const int MAXN = 40005 ;

struct type
{
    int  end , next ;
    int  w ;
} ;

type  edge[MAXN*2] , qedge[MAXN*2] ;
int   M , N , K ;
int   head[MAXN] , Count , qcnt , qhead[MAXN] ;
int   dis[MAXN] , father[MAXN] , ans[MAXN] , rank[MAXN] ;
bool  vis[MAXN]  ;

void  addedge( int start , int end , int w )
{
    edge[Count].end  = end         ;
    edge[Count].w    = w           ;
    edge[Count].next = head[start] ;
    head[start]      = Count ++    ;
}

void  qadd( int start , int end , int w )
{
    qedge[qcnt].end  = end          ;
    qedge[qcnt].w    = w            ;
    qedge[qcnt].next = qhead[start] ;
    qhead[start]     = qcnt ++      ;
}

int  find( int x )
{
    if( father[x] == -1 ) return x ;
    father[x] = find( father[x] )  ;
    return father[x]               ;
}

void  tarjan( int start , int disnow )
{
    int  i , j , end , w ;

    dis[start] = disnow  ;
    vis[start] = 1       ;
    for( i = qhead[start] ; i != -1 ; i = qedge[i].next )
    {
        end = qedge[i].end ;
        w   = qedge[i].w   ;
        if( vis[end] ) ans[w] = dis[start] + dis[end] - 2 * dis[find(end)] ;
    }
    for( i = head[start] ; i != -1 ; i = edge[i].next )
    {
        end = edge[i].end ;
        w   = edge[i].w   ;
        if( !vis[end] )
        {
            tarjan( end , disnow + w ) ;
            father[end] = start        ;
        }
    }
}

int  main()
{
    int   i , j ;
    int   start , end , dis ;
    char  ch ;

    while( scanf( "%d%d" , & N , & M ) != EOF )
    {
        memset( head   , -1 , sizeof( head   ) ) ;
        memset( qhead  , -1 , sizeof( qhead  ) ) ;
        memset( father , -1 , sizeof( father ) ) ;
        memset( rank   , 0  , sizeof( rank   ) ) ;
        memset( vis    , 0  , sizeof( vis    ) ) ;
        Count = 0 , qcnt = 0 ;

        while( M -- )
        {
            scanf( "%d %d %d %c" , & start , & end , & dis , & ch ) ;
            addedge( start , end , dis ) ;
            addedge( end , start , dis ) ;
        }

        scanf( "%d" , & K ) ;

        for( i = 1 ; i <= K ; i ++ )
        {
            scanf( "%d%d" , & start , & end ) ;
            qadd( start , end , i ) ;
            qadd( end , start , i ) ;
        }

        tarjan( 1 , 0 ) ;

        for( i = 1 ; i <= K ; i ++ )
            printf( "%d\n" , ans[i] ) ;
    }
    return 0 ;
}