POJ 3114 Countries in War（强联通分量+Tarjan）

浏览数：36 / 时间：2015年06月11日

http://poj.org/problem?id=3114

题意： n个城市，给出你m个关系，代表这城市x到城市y需要h小时，但如果两个城市是联通的，则耗时变为0，给你两个城市的编号，问你从前一个城市到后一个城市需要花费多长时间。

思路：我能说这个代码我直接将3592的代码一改就是这个了，那个求最长路，这个求最短路，把松弛那块儿改一下就行。反正先建图，将联通的点缩成一个联通分量，求的时候凡是一个联通分量时间就为0。

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;

const int maxn = 335555 ;
const int INF = 1000000000 ;

int belong[maxn],instack[maxn],dfn[maxn],low[maxn] ;
int cntt,cnt,top,bcc_clock,cntb,n,m;
int head1[maxn] ,head[maxn];
int dis[maxn],coun[maxn] ;
bool vis[maxn],flag[maxn] ;

struct node
{
    int u,v,w,next ;
} p[maxn] ,ch[maxn];

void addedge(int u,int v,int w)
{
    p[cnt].u = u ;
    p[cnt].v = v ;
    p[cnt].w = w ;
    p[cnt].next = head[u] ;
    head[u] = cnt++ ;
}

void addnode(int u,int v,int w)
{
    ch[cntt].u = u ;
    ch[cntt].v = v ;
    ch[cntt].w = w ;
    ch[cntt].next = head1[u] ;
    head1[u] = cntt++ ;
}

void tarjan(int u)
{
    vis[u] = true ;
    dfn[u] = low[u] = ++bcc_clock ;
    instack[++top] = u ;
    for(int i = head[u] ; i+1 ; i = p[i].next)
    {
        int v = p[i].v ;
        if(!dfn[v])
        {
            tarjan(v) ;
            low[u] = min(low[u],low[v]) ;
        }
        else if(vis[v])
            low[u] = min(low[u],dfn[v]) ;
    }
    if(dfn[u] == low[u])
    {
        cntb++ ;
        int v ;
        do
        {
            v = instack[top--] ;
            vis[v] = false ;
            belong[v] = cntb ;
        }
        while(v != u) ;
    }
}

void Init()
{
    memset(dfn,0,sizeof(dfn)) ;
    memset(low,0,sizeof(low)) ;
    memset(belong,0,sizeof(belong)) ;
    memset(vis,0,sizeof(vis)) ;
    memset(head,-1,sizeof(head)) ;
    memset(head1,-1,sizeof(head1)) ;
    cnt = 0,top = 0 ,cntb = 0,bcc_clock = 0,cntt = 0 ;
}

bool relax(int u,int v,int w)
{
    if(dis[v] > dis[u] + w)
    {
        dis[v] = dis[u] + w ;
        return true ;
    }
    return false ;
}

bool spfa(int u)
{
    memset(flag,false,sizeof(flag)) ;
    memset(coun,0,sizeof(coun)) ;
    flag[u] = true ;
    for(int i = 0 ; i <= n; i++)
        dis[i] = INF ;
    queue<int >Q ;
    Q.push(u) ;
    dis[u] = 0 ;
    while(!Q.empty ())
    {
        int st = Q.front() ;
        Q.pop() ;
        flag[st] = false ;
        for(int i = head1[st] ; i+1 ; i = ch[i].next)
        {
            if(relax(st,ch[i].v,ch[i].w) && !flag[ch[i].v])
            {
                if((++coun[ch[i].v]) > n) return false ;
                Q.push(ch[i].v) ;
                flag[ch[i].v] = true ;
            }
        }
    }
    return true ;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        if(n == 0 && m == 0) break ;
        Init() ;
        int u,v,w ;
        for(int i = 0 ; i < m ; i++)
        {
            scanf("%d %d %d",&u,&v,&w) ;
            addedge(u,v,w) ;
        }
        for(int i = 1 ; i <= n ; i++)
        {
            if(!dfn[i])
                tarjan(i) ;
        }
        for(int i = 1 ; i <= n; i++)
        {
            for(int j = head[i] ; j + 1 ; j = p[j].next)
            {
                int v = p[j].v ;
                if(belong[i] != belong[v])
                    addnode(i,v,p[j].w) ;
                else addnode(i,v,0) ;
            }
        }
        int x ,O,D;
        scanf("%d",&x) ;
        for(int i = 0 ; i < x ; i++)
        {
            scanf("%d %d",&O,&D) ;
            spfa(O) ;
            if(dis[D] != INF)
                printf("%d\n",dis[D]) ;
            else
                printf("Nao e possivel entregar a carta\n") ;
        }
        printf("\n") ;
    }
    return 0;
}