【連通圖|強連通分量+最長路】POJ-3592 Instantaneous Transference

Instantaneous Transference

Time Limit: 5000MS Memory Limit: 65536K

Description

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.

Input

The first line of the input is an integer T which indicates the number of test cases.

For each of the test case, the first will be two integers N, M (2 ≤ N, M ≤ 40).

The next N lines will describe the map of the mine field. Each of the N lines will be a string that contains M characters. Each character will be an integer X (0 ≤ X ≤ 9) or a ‘’ or a ‘#’. The integer X indicates that square has X units of ores, which your truck could get them all. The ‘’ indicates this square has a magic power which can transfer truck within an instant. The ‘#’ indicates this square is full of rock and the truck can’t move on this square. You can assume that the starting position of the truck will never be a ‘#’ square.

As the map indicates, there are K ‘’ on the map. Then there follows K lines after the map. The next K lines describe the specified target coordinates for the squares with ‘‘, in the order from north to south then west to east. (the original point is the northwest corner, the coordinate is formatted as north-south, west-east, all from 0 to N - 1,M - 1).

Output

For each test case output the maximum units of ores you can take. 　

Sample Input

1

2 2

11

1*

0 0

Sample Output

3

Source

South Central China 2008 hosted by NUDT

題意： 給出一個有向圖，其中每個點向自己下面的和右邊的那個點有邊相連。’*’号的點可以進行瞬間轉移（可以選擇轉移或者不轉移），每個點有點權且不為負。’#’号的點是不能到達的點。每到一個點獲得它的權值且僅一次，求出能獲得的最大點權和。

思路： 其實本來我是拒絕用強連通分量做這道題的，但是導演說，做完加特技……Duang~

看了樣例就會發現這個求最長路的題目存在正環。那麼用強連通分量可以把所有的環縮成一個點，然後重建立圖，跑一遍spfa即可。

注意： ‘#’結點不向其它的點連邊即可，一開始我是其它的點不向’#’連邊，WA了，我猜是因為有些瞬間轉移牽扯到了’#’。

代碼如下：

/*
 * ID: j.sure.1
 * PROG:
 * LANG: C++
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#define PB push_back
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
/****************************************/
const int N = 2e3+5, M = 3*N;
int r, c;
int n;
int head[N], dfn[N], scc_id[N], sum[N];
int scc_cnt, deep, tot, poi;
struct Edge {
    int v, next;
    Edge(){}
    Edge(int _v, int _next):
        v(_v), next(_next){}
}e[M];

void init()
{
    poi = tot = deep = scc_cnt = 0;
    memset(head, -1, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    memset(scc_id, 0, sizeof(scc_id));
    memset(sum, 0, sizeof(sum));
}

void add(int u, int v)
{
    e[tot] = Edge(v, head[u]);
    head[u] = tot++;
}

int w[N], trans[N];
void input()
{
    char str[50];
    for(int i = 0; i < r; i++) {
        scanf("%s", str);
        for(int j = 0; j < c; j++) {
            int u = i * c + j;
            if(str[j] == '*') {
                w[u] = 0;
                trans[poi++] = u;
            }
            else if(str[j] == '#') {
                w[u] = -1;
            }
            else {
                w[u] = str[j] - '0';
            }
        }
    }
}

void build()
{
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            int u = i * c + j;
            if(~w[u]) {
                if(j != c-1) add(u, u+1);
                if(i != r-1) add(u, u+c);
            }
        }
    }
    int x, y;
    for(int i = 0; i < poi; i++) {
        scanf("%d%d", &x, &y);
        int v = x * c + y;
        add(trans[i], v);
    }   
}

stack <int> s;
int dfs(int u)
{
    int lowu = dfn[u] = ++deep;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].v;
        if(!dfn[v]) {
            int lowv = dfs(v);
            lowu = min(lowu, lowv);
        }
        else if(!scc_id[v]) {
            lowu = min(lowu, dfn[v]);
        }
    }
    if(lowu == dfn[u]) {
        scc_cnt++;
        while(1) {
            int x = s.top(); s.pop();
            scc_id[x] = scc_cnt;//nmuber from 1
            sum[scc_cnt] += w[x];
            if(x == u) break;
        }
    }
    return lowu;
}

void tarjan()
{
    for(int i = 0; i < n; i++) {
        if(!dfn[i]) dfs(i);
    }
}

vector <int> ef[N];
void rebuild()
{
    for(int i = 1; i <= scc_cnt; i++) {
        ef[i].clear();
    }
    for(int u = 0; u < n; u++) {
        for(int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if(scc_id[u] != scc_id[v]) {
                ef[scc_id[u]].PB(scc_id[v]);
            }
        }
    }
}

int dis[N];//!
bool inq[N];//!
void spfa(int st)
{
    memset(dis, 0, sizeof(dis));
    queue <int> q;
    q.push(st);
    inq[st] = true;
    dis[st] = sum[st];
    while(!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        size_t len = ef[u].size();
        for(size_t i = 0; i < len; i++) {
            int v = ef[u][i];
            if(dis[v] < dis[u] + sum[v]) {
                dis[v] = dis[u] + sum[v];
                if(!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

int solve()
{
    rebuild();
    spfa(scc_id[0]);
    int ret = 0;
    for(int i = 1; i <= scc_cnt; i++) {
        ret = max(ret, dis[i]);
    }
    return ret;
}

int main()
{
#ifdef J_Sure
    freopen("000.in", "r", stdin);
    //freopen("999.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &r, &c);
        n = r * c;
        init();
        input();
        build();
        tarjan();
        int ans = solve();
        printf("%d\n", ans);
    }
    return 0;
}