题目链接：
?id=3592
题目大意：
有一个N*M的矩阵地图，矩阵中用了多种字符代表不同的地形，如果是数字X(0~9)，则表示
该区域为矿区，有X单位的矿产。如果是"*"，则表示该区域为传送点，并且对应唯一一个目标
坐标。如果是"#",，则表示该区域为山区，矿车不能进入。现在矿车的出发点在坐标(0，0)点。
并且(0，0)点一定不是"#"区域。矿车只能向右走、向下走或是遇到传送点的时候可以传送到
指定位置。那么问题来了：矿车最多能采到多少矿。
思路：
如果把N*M个矩阵单位看做是N*M个点，编号为0~N*M。然后从一个坐标到另一个坐标看做
是两点之间的边。到达的坐标所拥有的矿产为边的权值。那么问题就变成了：矿车从节点0出发，
所能达到的最长路径。但是除了向右走和向下走的边，考虑到还有传送点和目标坐标构成的边，
原图上就会多了很多回退边，构成了很多的有向环。有向环的出现，使得矿车能够采到的矿产
增多了一部分，只要能走到有向环内，则该环内所有点的矿产都能被采到。但是问题也出来了，
如果不做处理，直接搜索路径，，那么矿车很可能会走进环内不出来。
于是想到了缩点，把有向环缩为一个点，也就是强连通分量缩点。并记录强连通分量中的总矿产
值。缩点后，原图就变成了一个有向无环图(DAG)。然后重新建立一个新图(DAG)，对新图求最
长路径(用SPFA算法)，得到源点(0，0)到各点的最长路径。从中找出最长的路径，就是所求的结
果。
需要注意很多点：
1."*"区域能够传送到"#"区域。。。
2.矿车开始的地方是(0，0)
3.有多组数据，一定注意数据的清空
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int MAXN = 1610;const int MAXM = 50050;const int INF = 0xffffff0;struct EdgeNode{int to;int next;}Edges[MAXM],Edges1[MAXM];//存放原图，新图int Head[MAXN],Head1[MAXN];int vis[MAXN],vist[MAXN];//标记访问int dfn[MAXN],low[MAXN],belong[MAXN]; //开始访问时间次序，栈中最早访问时间int Stack[MAXN];//缩点用到的栈int m,id,ip,scc,lay,N,M;//id原图边数，ip新图边数int cost[MAXN],sum[MAXN]; //cost为原图每点的值，sum为强连通分量的值char Map[50][50];//存放原图int Dist[MAXN],outque[MAXN];void AddEdges(int u,int v) //原图加边{Edges[id].to = v;Edges[id].next = Head[u];Head[u] = id++;}void AddEdges1(int u,int v) //新图加边{Edges1[ip].to = v;Edges1[ip].next = Head1[u];Head1[u] = ip++;}int TarBFS(int pos){int v;vis[pos] = 1;low[pos] = dfn[pos] = ++lay;Stack[m++] = pos;for(int i = Head[pos]; i != -1; i = Edges[i].next){int v = Edges[i].to;if( !dfn[v] ){TarBFS(v);low[pos] = min(low[pos], low[v]);}else if( vis[v] )low[pos] = min(low[pos], low[v]);}if(dfn[pos] == low[pos]){++scc;do{v = Stack[–m];sum[scc] += cost[v];belong[v] = scc;vis[v] = 0;}while(v != pos);}return 0;}void ReBuildMap()//重建新图(DAG){ip = 0;for(int u = 0; u < N*M; ++u)for(int k = Head[u]; k != -1; k = Edges[k].next){int v = Edges[k].to;if(belong[u] != belong[v])AddEdges1(belong[u],belong[v]);}}void SPFA()//求最长路{memset(vist,0,sizeof(vist));memset(Dist,0,sizeof(Dist));queue<int> Q;Q.push(belong[0]);vist[belong[0]] = 1;Dist[belong[0]] = sum[belong[0]];while( !Q.empty() ){int u = Q.front();Q.pop();vist[u] = 0;for(int i = Head1[u]; i != -1; i = Edges1[i].next){int v = Edges1[i].to;if(Dist[v] < Dist[u] + sum[v]){Dist[v] = Dist[u] + sum[v];if( !vist[v] ){vist[v] = 1;Q.push(v);}}}}}int main(){int T,x,y;scanf("%d",&T);while(T–){scanf("%d%d",&N,&M);memset(Head,-1,sizeof(Head));memset(Head1,-1,sizeof(Head1));memset(cost,0,sizeof(cost));memset(vis,0,sizeof(vis));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(sum,0,sizeof(sum));for(int i = 0; i < N; ++i)scanf("%s",Map[i]);for(int i = 0; i < N; ++i){for(int j = 0; j < M; ++j){if(Map[i][j] != '#'){if(i+1 < N && Map[i+1][j] != '#') //向下走AddEdges(i*M+j,(i+1)*M+j);if(j+1 < M && Map[i][j+1] != '#') //向右走AddEdges(i*M+j,i*M+j+1);cost[i*M+j] = Map[i][j] – '0';if(Map[i][j] == '*'){cost[i*M+j] = 0;scanf("%d%d",&x,&y);if(Map[x][y] != '#')AddEdges(i*M+j,x*M+y);}}}}scc = id = m = lay = 0;for(int i = 0; i < N*M; ++i)if(!dfn[i])TarBFS(i);ReBuildMap();SPFA();int ans = -1;for(int i = 1; i <= scc; ++i)if(ans < Dist[i])ans = Dist[i];printf("%d\n",ans);}return 0;}/*10010 1012345678*02345678901345678*012456*89012356789012346789*123457890123456890*234567901234*6780123*567892 23 34 45 56 67 78 83 3*1*2*111*1 12 21 31 1答案为：1245*/失败代码：
有时，明知错了，却欲罢不能，
