题目大意：有一张n*m的地图，每个点上可能是数字，代表矿石的数目，，可能是*，表示一个传送阵，送往某个坐标，可能是#，代表不通。每次矿车只能往右方或者下方走一格，问从（0，0）点出发可以最多收集到多少矿石
思路：先根据矿车的可移动的方向建有向图，“*”导致可能会有环，所以先缩点变成有向无环图。
然后就是DAG上的最长路问题（拓扑排序+dp）
而且也是单源最长路问题，可以用最短路算法去做
吐槽一下debug了一天，原来是tarjan的时间戳写跪了，关键是直到现在仍不觉得那种写法是错的，对拍了好久都没找到wa的数据，还是别用奇葩的思维写比较好，下次直接把index定义成全局，再全程++
方法一：（topsort+dp）
//368K16MSC++3089B#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;#define MAXM 55555const int N = 1666;char mp[45][45];int tran[N];int poi;int w[N],nw[N];int dfn[N],low[N],col[N];vector<int>es[N];vector<int>nes[N];int indeg[N];int sta[N],top;int num;int n,m;int tmp[N];int index;void tarjan(int u){dfn[u]=low[u]=++index;sta[++top]=u;tmp[u]=1;int sz=es[u].size();for(int i=0;i<sz;i++){int v=es[u][i];if(tmp[v]==0) tarjan(v);if(tmp[v]==1) low[u]=min(low[u],low[v]);}if(dfn[u]==low[u]){num++;while(1){int v=sta[top];col[v]=num;tmp[v]=2;nw[num]+=w[v];if(sta[top–]==u) break;}}}void buildmap(){int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){poi++;if(mp[i][j]=='#') continue;if(mp[i][j]=='*') w[poi]=0,tran[++cnt]=poi;if(mp[i][j]>='0'&&mp[i][j]<='9') w[poi]=mp[i][j]-'0';if(i+1<=n&&mp[i+1][j]!='#') es[poi].push_back(poi+m);if(j+1<=m&&mp[i][j+1]!='#') es[poi].push_back(poi+1);}for(int i=1;i<=cnt;i++){int x,y;scanf("%d%d",&x,&y);x++,y++;if(mp[x][y]=='#') continue;es[tran[i]].push_back((x-1)*m+y);}for(int i=1;i<=poi;i++) if(dfn[i]==0) index=0,tarjan(i);for(int i=1;i<=num;i++) nes[i].clear();for(int u=1;u<=poi;u++){int sz=es[u].size();for(int j=0;j<sz;j++){int v=es[u][j];if(col[u]==col[v]) continue;nes[col[u]].push_back(col[v]);indeg[col[v]]++;}}}int q[MAXM],h,t;int dp[N];void topsort(){for(int i=1;i<=num;i++)if(indeg[i]==0) q[t++]=i;while(h<t){int u=q[h++];int sz=nes[u].size();for(int i=0;i<sz;i++){int v=nes[u][i];indeg[v]–;if(indeg[v]==0) q[t++]=v;}}for(int i=t-1;i>=0;i–){int u=q[i];dp[u]=nw[u];int sz=nes[u].size();int tmp=0;for(int j=0;j<sz;j++){int v=nes[u][j];tmp=max(tmp,dp[v]);}dp[u]+=tmp;}}void ini(){memset(mp,0,sizeof(mp));memset(dfn,0,sizeof(dfn));memset(nw,0,sizeof(nw));memset(w,0,sizeof(w));for(int i=1;i<=n*m;i++) es[i].clear();memset(indeg,0,sizeof(indeg));poi=num=top=h=t=index=0;memset(dp,0,sizeof(dp));memset(tmp,0,sizeof(tmp));}int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);ini();for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);buildmap();topsort();printf( "%d\n",dp[col[1]] );}return 0;}方法二：（单源最短路算法）
//364K16MSC++3118B#include<cstdio>#include<cstring>#include<iostream>#include<cstring>#include<vector>#include<queue>using namespace std;#define MAXM 55555const int N = 1666;vector<int> es[N];char mp[45][45];int n,m,poi;int index;int tran[N],w[N];bool vis[N];int sta[N],top,col[N],dfn[N],low[N],num;struct Edge{int u,w;Edge(){};Edge(int a,int b){u=a,w=b;};};vector<Edge>nes[N];int nw[N];void tarjan(int u){dfn[u]=low[u]=++index;sta[++top]=u;int sz=es[u].size();for(int i=0;i<sz;i++){int v=es[u][i];if(vis[v]) continue;if(dfn[v]==0) tarjan(v);if(dfn[v]) low[u]=min(low[u],low[v]);}if(low[u]==dfn[u]){num++;while(1){int v=sta[top];vis[v]=1;col[v]=num;nw[num]+=w[v];if(sta[top–]==u) break;}}}void buildmap(){int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int u=(i-1)*m+j;if( mp[i][j]=='#' ) continue;if( mp[i][j]=='*' ) tran[++cnt]=u,w[u]=0;if( mp[i][j]>='0'&&mp[i][j]<='9' ) w[u]=mp[i][j]-'0';if(i+1<=n&&mp[i+1][j]!='#') es[u].push_back(u+m);if(j+1<=m&&mp[i][j+1]!='#') es[u].push_back(u+1);}for(int i=1;i<=cnt;i++){int x,y;scanf("%d%d",&x,&y);x++,y++;if(mp[x][y]!='#') es[tran[i]].push_back((x-1)*m+y);}for(int i=1;i<=poi;i++)if(dfn[i]==0) tarjan(i);for(int i=0;i<=num;i++) nes[i].clear();for(int u=1;u<=poi;u++){int sz=es[u].size();for(int j=0;j<sz;j++){int v=es[u][j];if(col[v]==col[u]) continue;nes[col[u]].push_back(Edge(col[v],nw[col[v]]));}}nes[0].push_back(Edge(col[1],nw[col[1]]));}int dis[N];int q[MAXM],h,t;bool book[N];void spfa(){for(int i=1;i<=num;i++) dis[i]=-1,book[i]=0;dis[0]=0;q[t++]=0;while(h<t){int cur=q[h++];book[cur]=0;int sz=nes[cur].size();for(int i=0;i<sz;i++){int v=nes[cur][i].u,w=nes[cur][i].w;if(dis[v]<dis[cur]+w){dis[v]=dis[cur]+w;if(!book[v]) book[v]=1,q[t++]=v;}}}}void ini(){poi=n*m;for(int i=0;i<=poi;i++) es[i].clear();memset(mp,-1,sizeof(mp));memset(w,-1,sizeof(w));memset(dfn,0,sizeof(dfn));memset(vis,0,sizeof(vis));memset(nw,0,sizeof(nw));h=t=num=top=index=0;}int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);ini();for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);buildmap();spfa();int ans=0;for(int i=1;i<=num;i++)ans=max(ans,dis[i]);printf("%d\n",ans);}return 0;}
击败不等于击倒，跌倒了，爬起来，想一想，为什么跌倒了，
