POJ3592 Instantaneous Transference - Tarjan缩点+DP

题目连接

http://poj.org/problem?id=3592

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

题意

采矿车只能向右或者向下移动,在传送点的时候可以进行瞬间移动到地图上的某一点,传送点可以用无数次,并且采矿车不能进入到山区,问你最大采矿量是多少。

题解

开始的时候以为矿车不会被传送到山区,连边的时候就没有多想什么,给山区也连了出边WA了一发,果然还是太年轻。

建边有两种可行的方式:

1.对点跑DFS跑到的点全部与DFS起点连单向边(只能右、下移动),连过边的做标记,最后给传送点连边即可。

2.N^连边,枚举每个点可走的点直接连边即可。

首先将地图染色,标记不同的连通分量,每个分量的矿产总量作为缩点后SCC图的权,而且由于传送无限次,必定可以都采完。那么现在只有对SCC图跑一次最大权路就可以了。题目没有规定终点,而且SCC图是简单无环图(DAG),所以我们只要重新建图后跑一边记忆化搜索记录根(起点所在的连通分量)到叶子结点路劲的权值和,DP出最大值就可以了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <stack>
using namespace std;
const int maxn = 2500+10;
int id,n,m,G[45][45],head[maxn],transnum[maxn],iid,hhead[maxn];
int dfn[maxn],low[maxn],flag[maxn],tot,vis[maxn],tag,w[maxn],dp[maxn];
int dx[2]={1,0},dy[2]={0,1};
stack<int> S;
struct Edge{
int from,next,to;
}E[maxn<<2],e[maxn<<2];
void init(){
id=0,tag=0,tot=0,iid=0;
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(head,-1,sizeof head);
memset(hhead,-1,sizeof hhead);
memset(vis,0,sizeof vis);
memset(flag,0,sizeof flag);
memset(transnum,0,sizeof transnum);
memset(w,0,sizeof w);
memset(G,0,sizeof G);
}
int point(int x,int y){
return x*m + y;
}
bool judge(int x,int y){
return x>=0 && x<n && y>=0 && y<m && G[x][y]!=-1;
}
void addEdge(int u,int v){
E[id].from=u;
E[id].to=v;
E[id].next=head[u];
head[u]=id++;
}
void addEdge2(int u,int v){
e[iid].from=u;
e[iid].to=v;
e[iid].next=hhead[u];
hhead[u]=iid++;
}
int askw(int num){
int y = num % m ;
int x = (num-y)/m ;
if(G[x][y]>0)
return G[x][y];
else
return 0;
}
void tarjan(int x){
dfn[x] = low[x] = ++tot;
vis[x] = 1;
S.push(x);
for(int i=head[x];i!=-1;i=E[i].next){
int v=E[i].to;
if(!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v])
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x]){
++tag;
while(1){
int now=S.top();
S.pop();
vis[now]=0;
flag[now]=tag;
w[tag] += askw(now);
if(now == x) break;
}
}
}
//记忆化DFS跑最短路用的
int dfs(int x){
if(dp[x]>-1)
return dp[x];
dp[x]=0;
for(int i=hhead[x];i!=-1;i=e[i].next)
dp[x]=max(dp[x],dfs(e[i].to));
dp[x]+=w[x];
return dp[x];
}
int main(){
int v;
scanf("%d",&v);
for(int cas=0;cas<v;++cas){
init();
scanf("%d%d",&n,&m);
char temp[maxn];
int num,transcnt=0;
for(int i=0;i<n;++i){
scanf("%s\n",temp);
for(int j=0;j<m;++j){
if(temp[j]=='#')
G[i][j]=-1;
else if(temp[j] == '*'){
transcnt++;
G[i][j]=0;
transnum[transcnt]=point(i,j);
}
else{
num=temp[j]-'0';
G[i][j]=num;
}
}
}
//建立图内连通。
for(int x=0;x<n;++x)
for(int y=0;y<m;++y) {
if(G[x][y]!=-1) {
for (int k = 0; k < 2; ++k) {
int tx = x + dx[k], ty = y + dy[k];
if (judge(tx, ty) && G[tx][ty] != -1) {
addEdge(point(x, y), point(tx, ty));
}
}
}
}
//建立传送门。
int u,r,pnum;
for(int i=1;i<=transcnt;++i){
scanf("%d%d",&u,&r);
pnum = point(u,r);
addEdge(transnum[i],pnum);
}
int total = maxn;
for(int i=0;i<maxn;++i)
if(!dfn[i])
tarjan(i);
//建立缩点图跑最长路用。
for(int i=0;i<id;++i){
u = flag[E[i].from],r=flag[E[i].to];
if(u!=r)
addEdge2(u,r);
}
//记忆化DFS跑DAG最短路(DP)。
for(int i=1;i<=tag;++i)
dp[i]=-1;
int ans = dfs(flag[0]);
printf("%d\n", ans);
}
}