POJ3592 Instantaneous Transference 強連通+最長路

題目連結：

poj3592

題意:

給出一幅n X m的二維地圖，每一個格子可能是礦區,障礙,或者傳送點 用不同的字元表示；

有一輛礦車從地圖的左上角（0,0）出發,僅僅能往右走或往下走，或者通過傳送點  選擇是否 傳送到特定地點

採過的礦的格子 礦會消失;問這輛礦車最多能採多少礦

解題思路:

首先又一次建圖,将圖中二維的頂點壓縮成一維的頂點             (友善Tarjan算法)

每一個頂點往右，下的頂點建邊，傳送點的格子往特定頂點建邊(建邊的兩端不能有障礙)

得到一幅可能存在環的有向圖;

由于採過礦的格子不能夠二次採礦,是以經過某個環等于採集了整個環中全部的礦

我們用Tarjan算法縮點 再又一次建圖

得到一幅無環有向圖，而圖中每條邊（u->v）的權值應等于value[v]

最後再用spfa求這幅圖的最長路就可以

代碼:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 1650
using namespace std;
struct node
{
    int to,next,w;
} edge1[maxn*3],edge2[maxn*3];
int head1[maxn],head2[maxn];
int s1,s2;

int dfn[maxn], low[maxn],num;

int sta[maxn],insta[maxn], top;

int belong[maxn],block;

int n,m,ss,v1[maxn],v2[maxn];
char map[45][45];

void init()
{
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
    memset(dfn,0,sizeof(dfn));
    memset(insta,0,sizeof(insta));
    memset(belong,0,sizeof(belong));
    memset(v2,0,sizeof(v2));
    s1=s2=num=top=block=0;
}

int judge(int x,int y)
{
    if(x<0||y<0||x>=n||y>=m)
        return -1;
    if(map[x][y]>='0'&&map[x][y]<='9')
        return 1;
    if(map[x][y]=='*')
        return 2;
    if(map[x][y]=='#')
        return -1;
}

void addedge(int d,int u,int v,int w)
{
    if(d==1){
        edge1[s1]={v,head1[u]};
        head1[u]=s1++;
    }
    else {
        edge2[s2]={v,head2[u],w};
        head2[u]=s2++;
    }
}

void Tarjan(int u,int pre)
{
    dfn[u]=low[u]=++num;
    insta[u]=1;
    sta[top++]=u;
    for(int i=head1[u];i!=-1;i=edge1[i].next)
    {
        int v=edge1[i].to;
        if(!dfn[v])
        {
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(insta[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])           //縮點
    {
        block++;
        int d=-1;
        while(d!=u)
        {
            d=sta[--top];
            insta[d]=0;
            belong[d]=block;
            v2[block]+=v1[d];
        }
    }
}

void rebuild()
{
    int u,v;
    for(int i=0;i<n*m;i++)
    {
        u=belong[i];
        for(int j=head1[i];j!=-1;j=edge1[j].next)
        {
            v=edge1[j].to;
            v=belong[v];
            if(u!=v)              //又一次建邊
                addedge(2,u,v,v2[v]);
        }
    }
}

void spfa()
{
    int u,v,start=belong[0];   //起點為（0,0）所在的強連通分量裡面
    queue<int>q;
    int vis[maxn]={0};
    int dis[maxn]={0};
    vis[start]=1;
    dis[start]=v2[start];
    q.push(start);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head2[u];i!=-1;i=edge2[i].next)
        {
            v=edge2[i].to;
            if(dis[v]<dis[u]+edge2[i].w)
            {
                dis[v]=dis[u]+edge2[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=block;i++)
        if(dis[i]>ans)
            ans=dis[i];
    cout<<ans<<endl;

}

int main()
{
    int T,s,ss,loc;
    char ch;
    int pos[maxn][2];
    scanf("%d",&T);
    while(T--)
    {
        s=1,ss=0;
        init();
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='*')
                    ss++;
            }
        for(int i=1; i<=ss; i++)                //記錄第i個傳送點的傳送位置
            scanf("%d%d",&pos[i][0],&pos[i][1]);

        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                loc=i*m+j;                            //一維頂點
                if(judge(i,j)==1)
                    v1[loc]=map[i][j]-'0';
                else if(judge(i,j)==2)
                    v1[loc]=0;                         //傳送點沒有礦
                if(judge(i,j)!=-1)
                {
                    if(judge(i+1,j)!=-1)               //下
                        addedge(1,loc,loc+m,0);
                    if(judge(i,j+1)!=-1)               //右
                        addedge(1,loc,loc+1,0);
                    if(judge(i,j)==2)                  //傳送點
                        addedge(1,loc,pos[s][0]*m+pos[s++][1],0);
                }
                else
                    v1[loc]=-1;       //障礙
            }

        for(int i=0;i<n*m;i++)
            if(!dfn[i]&&v1[i]!=-1)          //注意障礙不能進行Tarjan
                Tarjan(i,-1);
        rebuild();
        spfa();
    }
    return 0;
}
           

轉載于:https://www.cnblogs.com/zhchoutai/p/6830047.html