POJ--3592[Instantaneous Transference] 縮點+求最長路

思路：

(1):構完圖縮點然後求最長路

(2):注意*号的位置可以選擇不跳

(3):資料裡沒有*号跳到#号的情況

PS.說實話這題不難，思路和poj3160一樣、、

CODE:

/*縮點+求最長路*/
/*注意：*号的位置可以選擇不跳*/
/*AC代碼：16ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#include <algorithm>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define MAXN 1605
#define INF 1e8
using namespace std;
struct edge
{
    int u,v,w,next;
}E[200000],sE[200000];
int head[MAXN],ecnt;
int shead[MAXN],secnt;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN],num[MAXN];
int dis[MAXN];
int Index,scc,top,N,M,vn;
bool Instack[MAXN],vis[MAXN];
char map[50][50];
int W[MAXN],scr;
int ins[MAXN],cnt;
void Insert(int u,int v)
{
    E[ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].next=head[u];
    head[u]=ecnt++;
}
void sInsert(int u,int v,int w)
{
    sE[secnt].u=u;
    sE[secnt].v=v;
    sE[secnt].w=w;
    sE[secnt].next=shead[u];
    shead[u]=secnt++;
}
void Init()
{
    int i,j,u,v,x,y;
    memset(head,-1,sizeof(head));ecnt=0;
    memset(shead,-1,sizeof(shead));secnt=0;
    memset(W,0,sizeof(W));
    scanf("%d%d",&N,&M);
    vn=N*M;
    for(i=1;i<=N;i++)
        scanf("%s",map[i]+1);
    cnt=0;
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
        {
            u=(i-1)*M+j;
            if(map[i][j]=='#')
                W[u]=0;
            else if(map[i][j]=='*')
            {
                W[u]=0;
                ins[cnt++]=u;
                if(j<M&&map[i][j+1]!='#')
                    Insert(u,u+1);
                if(i<N&&map[i+1][j]!='#')
                    Insert(u,u+M);
            }
            else
            {
                W[u]=map[i][j]-'0';
                if(j<M&&map[i][j+1]!='#')
                    Insert(u,u+1);
                if(i<N&&map[i+1][j]!='#')
                    Insert(u,u+M);
            }
        }
    }
    /*
    for(i=0;i<ecnt;i++)
        printf("*%d %d\n",E[i].u,E[i].v);
    */
    for(i=0;i<cnt;i++)
    {
        scanf("%d%d",&x,&y);
        x++;y++;
        //if(map[x][y]=='#') continue;
        v=(x-1)*M+y;
        Insert(ins[i],v);
    }
}
void Tarjan(int u)
{
    int i,v;
    Low[u]=DFN[u]=++Index;
    Stack[++top]=u;
    Instack[u]=true;
    for(i=head[u];i!=-1;i=E[i].next)
    {
        v=E[i].v;
        if(!DFN[v])
        {
            Tarjan(v);
            if(Low[u]>Low[v])
                Low[u]=Low[v];
        }
        else if(Instack[v]&&Low[u]>DFN[v])
            Low[u]=DFN[v];
    }
    if(Low[u]==DFN[u])
    {
        scc++;
        do{
            v=Stack[top--];
            Instack[v]=false;
            Belong[v]=scc;
            num[scc]+=W[v];
        }while(u!=v);
    }
    return;
}
void Suo()//縮點+重新構圖
{
    int i,u,v;
    memset(num,0,sizeof(num));
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(Low,0,sizeof(Low));
    Index=scc=top=0;
    for(i=1;i<=vn;i++)//縮點
    {if(!DFN[i]) Tarjan(i);}
    //構新圖
    for(i=0;i<ecnt;i++)
    {
        u=E[i].u;v=E[i].v;
        if(Belong[u]!=Belong[v])
            sInsert(Belong[u],Belong[v],num[Belong[v]]);
    }
    //printf("$%d\n",scc);
}
queue<int>Q;
int SPFA(int s)
{
    int i,u,v,w;
    while(!Q.empty()) Q.pop();
    memset(vis,false,sizeof(vis));
    for(i=1;i<=scc;i++)
        dis[i]=-INF;
    Q.push(s);
    dis[s]=0;
    vis[s]=true;
    while(!Q.empty())
    {
        u=Q.front();Q.pop();
        vis[u]=false;
        for(i=shead[u];i!=-1;i=sE[i].next)
        {
            v=sE[i].v;w=sE[i].w;
            if(dis[v]<dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    Q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    int res=0;
    for(i=1;i<=scc;i++)
        res=max(res,dis[i]);
    return res+num[s];
}
void Solve()
{
    Suo();
    scr=Belong[1];
    int ans=SPFA(scr);
    printf("%d\n",ans);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        Init();
        Solve();
    }
return 0;
}