【题意】：给出一个n*m的矩阵，每个格子可能放有0~9，#，*。0~9代表货物的数量，#代表阻碍，不能够走，*代表传送点，可以瞬间传送到特定的位置，对于传送点的传送功能可以无限使用，也可以不用。初始时你开着一辆小卡车在最左上角，每一次你都可以向右走一格或者向下走一格，如果该格子上放有货物的话你可以把他拿走，但只能拿一次。问最后你能够拿到最多的货物是多少？
【题解】：这是一道方格取数的变形题目，加入了阻碍与传送点。如果按平时方格取数那样做的话，由于传送点的存在，图中可能有环从而导死循环。于是我们想到了缩点，缩点后的新图显然是一个有向无环图，对于同一连通分量上的货物我们都可以拿走，这里留给大家自己思考为什么了，之后该怎么做就怎么做了。实际操作时，我们可以先按平时的方格取数构图，对于传送点i，假设si是传送点的本身位置，ti是传送点的目标位置，连边si->ti，然后进行缩点构新图，缩点之后的做法有很多，DP、搜索、求最长路都可以，我这里是求最长路。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "vector"
5 #include "queue"
6 using namespace std;
7 #define maxn 1605
8 const int inf = 1 << 30;
9 struct Edge {
10 int v, w;
11 };
12 int n, m;
13 char maz[50][50];
14 int dfn[maxn], low[maxn], Dindex, scc, belong[maxn], dist[maxn], score[maxn], w[maxn];;
15 int magic[maxn], cnt;
16 int s[maxn], top;
17 bool instack[maxn], visit[maxn];
18 vector<int> vec[maxn];
19 vector<Edge> dag[maxn];
20
21 void dfs(int u) {
22 int v;
23 dfn[u] = low[u] = ++Dindex;
24 s[++top] = u;
25 instack[u] = true;
26 int size = vec[u].size();
27 for(int i = 0; i < size; i++) {
28 v = vec[u][i];
29 if(!dfn[v]) {
30 dfs(v);
31 low[u] = min(low[v], low[u]);
32 } else if(instack[v]) low[u] = min(low[u], dfn[v]);
33 }
34 if(dfn[u] == low[u]) {
35 w[++scc] = 0;
36 do {
37 v = s[top--];
38 instack[v] = false;
39 belong[v] = scc;
40 w[scc] += score[v];
41 }while(v != u);
42 }
43 }
44
45 void tarjan() {
46 top = scc = Dindex = 0;
47 memset(instack, false, sizeof(instack));
48 memset(dfn, 0, sizeof(dfn));
49 for(int i = 0; i < n * m; i++)
50 if(!dfn[i]) dfs(i);
51 for(int u = 0; u < n * m; u++) {
52 int size = vec[u].size();
53 for(int i = 0; i < size; i++) {
54 int v = vec[u][i];
55 if(belong[u] != belong[v]) {
56 Edge e = {belong[v], w[belong[v]]};
57 dag[belong[u]].push_back(e);
58 }
59 }
60 }
61 Edge e = {belong[0], w[belong[0]]};
62 dag[0].push_back(e);
63 }
64
65 int spfa(int s) {
66 fill(&dist[0], &dist[maxn], -inf);
67 memset(visit, false, sizeof(visit));
68 dist[s] = 0, visit[s] = true;
69 queue<int> que;
70 que.push(s);
71 while(!que.empty()) {
72 int u = que.front();
73 que.pop();
74 visit[u] = false;
75 int size = dag[u].size();
76 for(int i = 0; i < size; i++) {
77 int v = dag[u][i].v, w = dag[u][i].w;
78 if(dist[v] < dist[u] + w) {
79 dist[v] = dist[u] + w;
80 if(!visit[v]) {
81 que.push(v);
82 visit[v] = false;
83 }
84 }
85 }
86 }
87 int ans = 0;
88 for(int i = 0; i <= scc; i++)
89 ans = max(ans, dist[i]);
90 return ans;
91 }
92
93 int main() {
94 int T;
95 scanf("%d", &T);
96 while(T--) {
97 scanf("%d%d", &n, &m);
98 getchar();
99 cnt = 0;
100 for(int i = 0; i < maxn; i++) vec[i].clear(), dag[i].clear();
101 for(int i = 0; i < n; i++) scanf("%s", maz[i]);
102 for(int i = 0; i < n; i++) {
103 for(int j = 0; j < m; j++) {
104 int u = i * m + j;
105 if(maz[i][j] == '#') score[u] = -1;
106 else {
107 if(maz[i][j] == '*') {
108 magic[cnt++] = u;
109 score[u] = 0;
110 }
111 else score[u] = maz[i][j] - '0';
112 if(j + 1 < m && maz[i][j+1] != '#') vec[u].push_back(u + 1);
113 if(i + 1 < n && maz[i+1][j] != '#') vec[u].push_back(u + m);
114 }
115 }
116 }
117 for(int i = 0; i < cnt; i++) {
118 int ii, jj, v;
119 scanf("%d%d", &ii, &jj);
120 v = ii * m + jj;
121 if(score[v] == -1) continue;
122 vec[magic[i]].push_back(v);
123 }
124 tarjan(); //缩点构新图 - dag
125 cout << spfa(0) << endl;
126 }
127 return 0;
128 }