poj_3592 Instantaneous Transference

题目:

  It was long ago when we played the game Red Alert. There is a magic function for the game objects which is called instantaneous transfer. When an object uses this magic function, it will be transferred to the specified point immediately, regardless of how far it is.
  Now there is a mining area, and you are driving an ore-miner truck. Your mission is to take the maximum ores in the field.
  The ore area is a rectangle region which is composed by n × m small squares, some of the squares have numbers of ores, while some do not. The ores can't be regenerated after taken.
  The starting position of the ore-miner truck is the northwest corner of the field. It must move to the eastern or southern adjacent square, while it can not move to the northern or western adjacent square. And some squares have magic power that can instantaneously transfer the truck to a certain square specified. However, as the captain of the ore-miner truck, you can decide whether to use this magic power or to stay still. One magic power square will never lose its magic power; you can use the magic power whenever you get there.

思路:

  把每个点向它可以到达的点连边,那么问题就是找一条路径权值和最大。考虑缩点,在每个点上记录权值和。在DAG上求最=大权值和只要跑一次dp即可。因为起点一定是,所以要再bfs一遍计算入度。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <cctype>
#include <iostream>
#include <queue>
#define MN 1605
#define ll long long
#define clr(a,b) memset(a,b,sizeof a)
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
vector<int> G[MN],M[MN];
int dfn[MN],ble[MN],low[MN],val[MN],sum[MN],stk[MN],No,bcnt,tp;
void dfs(int o){
    dfn[o]=low[o]=++No;
    stk[++tp]=o;
    for(int i=0;i<G[o].size();i++){
        int v=G[o][i];
        if(!dfn[v]){
            dfs(v);
            tomin(low[o],low[v]);
        }
        else if(!ble[v])tomin(low[o],dfn[v]);
    }
    if(low[o]==dfn[o]){
        bcnt++;
        do {
            ble[stk[tp]]=bcnt;
            sum[bcnt]+=val[stk[tp]];
        }while(stk[tp--]!=o);
    }
}
int n,m,ind[MN];
void rebuild(){
    FOR(o,1,n*m)
        for(int i=0;i<G[o].size();i++){
            int v=G[o][i];
            if(ble[v]!=ble[o])
                M[ble[o]].push_back(ble[v]);
        }
}
bool vis[MN];
void bfs(){
    queue<int> q;
    q.push(ble[1]);vis[ble[1]]=1;
    while(!q.empty()){
        int o=q.front();q.pop();
        for(int i=0;i<M[o].size();i++){
            int v=M[o][i];
            if(!vis[v])q.push(v);
            ind[v]++;vis[v]=1;
        }
    }
}
int q[MN],dp[MN];
int Dp(){
    int hed=1,tai=0,ans=0;
    q[++tai]=ble[1];
    dp[ble[1]]=sum[ble[1]];
    while(hed<=tai){
        int o=q[hed++];
        tomax(ans,dp[o]);
        for(int i=0;i<M[o].size();i++){
            int v=M[o][i];
            tomax(dp[v],dp[o]+sum[v]);
            if(!--ind[v])q[++tai]=v;
        }
    }
    return ans;
}
char mp[45][45];
void clear(){
    clr(dfn,0);clr(ble,0);
    clr(sum,0);clr(mp,'#');
    bcnt=No=0;clr(ind,0);
    clr(dp,0);clr(vis,0);
    FOR(i,1,n*m)G[i].clear(),M[i].clear();
}
int calc(int x,int y){return (x-1)*m+y;}
#define read(c) do c=getchar();while(!isdigit(c)&&c!='#'&&c!='*')
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        clear();
        FOR(x,1,n)FOR(y,1,m)
            read(mp[x][y]);
        FOR(x,1,n)FOR(y,1,m){
            if(mp[x+1][y]!='#'&&mp[x][y]!='#')
                G[calc(x,y)].push_back(calc(x+1,y));
            if(mp[x][y+1]!='#'&&mp[x][y]!='#')
                G[calc(x,y)].push_back(calc(x,y+1));
            if(isdigit(mp[x][y]))val[calc(x,y)]=mp[x][y]-'0';
            else val[calc(x,y)]=0;
            if(mp[x][y]=='*'){
                int a,b;
                scanf("%d%d",&a,&b);
                a++;b++;
                if(mp[a][b]!='#')
                    G[calc(x,y)].push_back(calc(a,b));
            }
        }
        if(mp[1][1]=='#'){
            puts("0");
            continue;
        }
        FOR(i,1,n*m)if(!dfn[i])
            dfs(i);
        rebuild();bfs();
        printf("%d\n",Dp());
    }
    return 0;
}