POJ 3592 Instantaneous Transference

targan，spfa

传送门：HustOJ

传送门：POJ

题意

一个N*M的矩阵，矩阵内每点可能是数字1~9：表示这点有数字个矿石，可能是*，表示这点是个超时空传送点，矩阵结束后按顺序给出传送点的传送目的地坐标，可能是#：表示该点不可达。

任何矿石点可以到达其右侧点或下侧点，只要右或下点不是#；传送点也可以到其右或下，只要右或下点不是#。

现在矿车在(0,0)，问矿车走一趟最多可以采多少矿。

思路

思路很简单，有向图先缩点变成DAG，每个连通分量内矿石一定全部可以采到，然后相当于DAG最长路。

矩阵每个点视作图中一点，按可达关系建边，保存每点的矿石数量。矩阵中（i，j）在图中编号i*m+j，m是一行的点数。传送点和不可达点的矿石数是0。建图后targar缩点，顺便求出每个新点（连通块）的矿石总数。按连通块编号建新图，跑SPFA。

细节挺多，coding时多加注意。

代码

#include <cstdio>
#include <cstdlib>
//#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>

//#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;

const int MAXN=*;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;

int sumval[MAXN];
int val[MAXN];
int tra[MAXN];
char mp[][];

struct Targan
{
    vector<int> G[MAXN];
    int pre[MAXN], lowlink[MAXN], sccno[MAXN], dfs_clock, scc_cnt;
    stack<int> S;
    void init()
    {
        for(int i=;i<MAXN;i++) G[i].clear();
        while(!S.empty()) S.pop();
    }
    void addedge(int a, int b) { G[a].push_back(b); }
    void dfs(int u)
    {
        pre[u]=lowlink[u]=++dfs_clock;
        S.push(u);
        for(int i=;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(!pre[v])
            {
                dfs(v);
                lowlink[u]=min(lowlink[u], lowlink[v]);
            }
            else if(!sccno[v])
            {
                lowlink[u]=min(lowlink[u], pre[v]);
            }
        }
        if(lowlink[u]==pre[u])
        {
            scc_cnt++;
            while()
            {
                int x=S.top();S.pop();
                sccno[x]=scc_cnt;
                sumval[scc_cnt]+=val[x];
                if(x==u) break;
            }
        }
    }
    void find_scc(int n)
    {
        dfs_clock=scc_cnt=;
        M(sccno, );M(pre, );
        for(int i=;i<n;i++)
            if(!pre[i])
                dfs(i);
    }
}targan;
struct Spfa
{
    vector<int>G[MAXN];
    int dis[MAXN], vis[MAXN];
    void init()
    {
        for(int i=;i<MAXN;i++) G[i].clear();
    }
    void addedge(int a, int b)
    {
        G[a].push_back(b);
    }
    void diy()
    {
        M(dis, );M(vis, );
        queue<int> que;
        que.push(targan.sccno[]);
        vis[targan.sccno[]]=;
        dis[targan.sccno[]]=sumval[targan.sccno[]];

        while(!que.empty())
        {
            int u=que.front();que.pop();vis[u]=;
            for(int i=;i<G[u].size();i++)
            {
                int v=G[u][i];
                if(dis[u]+sumval[v]>dis[v])
                {
                    dis[v]=dis[u]+sumval[v];
                    if(!vis[v])
                    {
                        que.push(v);
                        vis[v]=;
                    }
                }
            }
        }
    }
}spfa;

int main()
{
    //_;
    int T;scanf("%d", &T);
    while(T--)
    {
        targan.init();
        M(val, );M(mp, );M(tra, );M(sumval, );

        int n, m;scanf("%d%d", &n, &m);
        int trans=;
        for(int i=;i<n;i++) scanf("%s", mp[i]);
        for(int i=;i<n;i++)
        {
            for(int j=;j<m;j++)
            {
                if(mp[i][j]=='#') continue;
                else if(mp[i][j]=='*')
                {
                    int a, b;scanf("%d%d", &a, &b);

                    targan.addedge(i*m+j, a*m+b);
                    if(i+<n && mp[i+][j]!='#')
                        targan.addedge(i*m+j, (i+)*m+j);
                    if(j+<m && mp[i][j+]!='#')
                        targan.addedge(i*m+j, i*m+j+);
                }
                else
                {
                    int nnn=mp[i][j]-'0';
                    val[i*m+j]=nnn;
                    if(i+<n && mp[i+][j]!='#')
                        targan.addedge(i*m+j, (i+)*m+j);
                    if(j+<m && mp[i][j+]!='#')
                        targan.addedge(i*m+j, i*m+j+);
                }
            }
        }

        int v=n*m;
        targan.find_scc(v);
        spfa.init();

        for(int i=;i<v;i++)
        {
            for(int j=;j<targan.G[i].size();j++)
            {
                if(targan.sccno[i]!=targan.sccno[targan.G[i][j]])
                {
                    spfa.addedge(targan.sccno[i], targan.sccno[targan.G[i][j]]);
                }
            }
        }
        spfa.diy();
        int res=;
        for(int i=;i<=targan.scc_cnt;i++)
        {
            res=max(res, spfa.dis[i]);
        }
        printf("%d\n", res);
    }
    return ;
}