POJ 3592 Instantaneous Transference

本文从WordPress迁移而来, 查看全部WordPress迁移文章

强连通分量

题意:一个n行m列的矩阵图,上面有3种点,可能是数字x(0<=x<=9),表示这里有多少个矿石,#表示不能走到这点,*表示传送点,对应一个目标点,可以瞬间传送到目标点。你从(0,0)左上角处出发,行走的方向只能是向左或者向下,要求你走到某个地方(不一定是右下角),让你得到的矿石最多。一个地方的矿石只能采集一次,下次再去到那个点是没有矿石的。注意几点,传送点可能将你传送到#这种点,那么相当于这个传送点是多余的等于没用,另外在传送点可以选择传送或者不传送继续走。

分析:由于传送点的存在,可能使这个有向图构成环,进而可能产生强连通分量,所以先建图,进行一次强连通分量缩点,为什么缩点,因为易知,在一个强连通分量内的点都是可以全部到达的,所以这个点内的矿石都能采集到。缩点后得到一个DAG,对这个DAG重新建图,另外重新计算缩点后每个点有多少矿石(即原来小点的矿石和)。然后从点(0,0)缩点后所在那个大点出发,用BFS搜索,求一次最长路,再取最大值即可

这题总的来说也不算难,就Tarjan缩点+bfs搜索最长路

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
156
157
158
159
160
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
#define N 2100

char a[50][50];
vector<int>mp;
vector<int>e[N];
vector<int>ver[N];
stack<int>sta;
queue<int>que;
int row,col,n;
int dfn[N],low[N],belong[N],dcnt,bcnt;
int val[N],sv[N],d[N];
bool ins[N],inq[N];

void input()
{
cin >> row >> col;
n = row * col;
for(int i=0; i<n; i++) e[i].clear();
for(int r=0; r<row; r++) cin >> a[r];
for(int r=0; r<row; r++)
for(int c=0; c<col; c++)
if(a[r][c] != '#')
{
int x,y,v,u;
u = r * col + c;
if(r+1 < row && a[r+1][c] != '#')
{
v = (r+1) * col + c;
e[u].push_back(v);
}
if(c+1 < col && a[r][c+1] != '#')
{
v = r * col + c+1;
e[u].push_back(v);
}

if(a[r][c] >= '0' && a[r][c] <= '9')
val[u] = a[r][c] - '0';
else
{
val[u] = 0;
cin >> x >> y;
if(a[x][y] != '#')
{
v = x * col + y;
e[u].push_back(v);
}
}

}
}

void rebuild()
{
for(int i=1; i<=bcnt; i++) ver[i].clear();
for(int i=0; i<n; i++)
{
int u = belong[i];
for(int j=0; j<e[i].size(); j++)
{
int v = belong[e[i][j]];
if(u != v) ver[u].push_back(v);
}
}
}

void dfs(int u)
{
dfn[u] = low[u] = ++dcnt;
sta.push(u); ins[u] = true;
for(int i=0; i<e[u].size(); i++)
{
int v = e[u][i];
if(!dfn[v])
{
dfs(v);
low[u] = min(low[u] , low[v]);
}
else if(ins[v]) low[u] = min(low[u] , dfn[v]);
}
if(low[u] == dfn[u])
{
++bcnt;
sv[bcnt] = 0;
while(true)
{
int x = sta.top();
sta.pop(); ins[x] = false;
belong[x] = bcnt;
sv[bcnt] += val[x];
if(x == u) break;
}
}
}

void Tarjan()
{
dcnt = bcnt = 0;
memset(dfn,0,sizeof(dfn));
memset(ins,false,sizeof(ins));
for(int i=0; i<n; i++)
if(!dfn[i])
dfs(i);
}

void bfs()
{
while(!que.empty()) que.pop();
memset(inq,false,sizeof(inq));
memset(d,-1,sizeof(d));
int s = belong[0];
d[s] = sv[s];
que.push(s);
inq[s] = 1;
while(!que.empty())
{
int u = que.front();
que.pop(); inq[u] = 0;
for(int i=0; i<ver[u].size(); i++)
{
int v = ver[u][i];
if(d[v] < d[u] + sv[v])
{
d[v] = d[u] + sv[v];
if(!inq[v])
{
inq[v] = 1;
que.push(v);
}
}
}
}
}

int main()
{
int cas;
cin >> cas;
while(cas--)
{
input();
Tarjan();
rebuild();
bfs();

int res = 0;
for(int i=1; i<=bcnt; i++)
res = max(res , d[i]);
cout << res << endl;
}
return 0;
}