题目链接：
题意:
给出一幅n X m的二维地图，每一个格子可能是矿区,障碍,或者传送点 用不同的字符表示；
有一辆矿车从地图的左上角（0,0）出发,仅仅能往右走或往下走，或者通过传送点 选择是否 传送到特定地点
採过的矿的格子 矿会消失;问这辆矿车最多能採多少矿
解题思路:
首先又一次建图,将图中二维的顶点压缩成一维的顶点 (方便Tarjan算法)
每一个顶点往右，下的顶点建边，传送点的格子往特定顶点建边(建边的两端不能有障碍)
得到一幅可能存在环的有向图;
由于採过矿的格子不能够二次採矿,所以经过某个环等于採集了整个环中全部的矿
我们用Tarjan算法缩点 再又一次建图
得到一幅无环有向图，而图中每条边（u->v）的权值应等于value[v]
最后再用spfa求这幅图的最长路就可以
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 1650
using namespace std;
struct node
{
int to,next,w;
} edge1[maxn*3],edge2[maxn*3];
int head1[maxn],head2[maxn];
int s1,s2; int dfn[maxn], low[maxn],num; int sta[maxn],insta[maxn], top; int belong[maxn],block; int n,m,ss,v1[maxn],v2[maxn];
char map[45][45]; void init()
{
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(dfn,0,sizeof(dfn));
memset(insta,0,sizeof(insta));
memset(belong,0,sizeof(belong));
memset(v2,0,sizeof(v2));
s1=s2=num=top=block=0;
} int judge(int x,int y)
{
if(x<0||y<0||x>=n||y>=m)
return -1;
if(map[x][y]>='0'&&map[x][y]<='9')
return 1;
if(map[x][y]=='*')
return 2;
if(map[x][y]=='#')
return -1;
} void addedge(int d,int u,int v,int w)
{
if(d==1){
edge1[s1]={v,head1[u]};
head1[u]=s1++;
}
else {
edge2[s2]={v,head2[u],w};
head2[u]=s2++;
}
} void Tarjan(int u,int pre)
{
dfn[u]=low[u]=++num;
insta[u]=1;
sta[top++]=u;
for(int i=head1[u];i!=-1;i=edge1[i].next)
{
int v=edge1[i].to;
if(!dfn[v])
{
Tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else if(insta[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) //缩点
{
block++;
int d=-1;
while(d!=u)
{
d=sta[--top];
insta[d]=0;
belong[d]=block;
v2[block]+=v1[d];
}
}
} void rebuild()
{
int u,v;
for(int i=0;i<n*m;i++)
{
u=belong[i];
for(int j=head1[i];j!=-1;j=edge1[j].next)
{
v=edge1[j].to;
v=belong[v];
if(u!=v) //又一次建边
addedge(2,u,v,v2[v]);
}
}
} void spfa()
{
int u,v,start=belong[0]; //起点为（0,0）所在的强连通分量里面
queue<int>q;
int vis[maxn]={0};
int dis[maxn]={0};
vis[start]=1;
dis[start]=v2[start];
q.push(start);
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=0;
for(int i=head2[u];i!=-1;i=edge2[i].next)
{
v=edge2[i].to;
if(dis[v]<dis[u]+edge2[i].w)
{
dis[v]=dis[u]+edge2[i].w;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
int ans=0;
for(int i=1;i<=block;i++)
if(dis[i]>ans)
ans=dis[i];
cout<<ans<<endl; } int main()
{
int T,s,ss,loc;
char ch;
int pos[maxn][2];
scanf("%d",&T);
while(T--)
{
s=1,ss=0;
init();
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>map[i][j];
if(map[i][j]=='*')
ss++;
}
for(int i=1; i<=ss; i++) //记录第i个传送点的传送位置
scanf("%d%d",&pos[i][0],&pos[i][1]); for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
loc=i*m+j; //一维顶点
if(judge(i,j)==1)
v1[loc]=map[i][j]-'0';
else if(judge(i,j)==2)
v1[loc]=0; //传送点没有矿
if(judge(i,j)!=-1)
{
if(judge(i+1,j)!=-1) //下
addedge(1,loc,loc+m,0);
if(judge(i,j+1)!=-1) //右
addedge(1,loc,loc+1,0);
if(judge(i,j)==2) //传送点
addedge(1,loc,pos[s][0]*m+pos[s++][1],0);
}
else
v1[loc]=-1; //障碍
} for(int i=0;i<n*m;i++)
if(!dfn[i]&&v1[i]!=-1) //注意障碍不能进行Tarjan
Tarjan(i,-1);
rebuild();
spfa();
}
return 0;
}