这道题的题意为：
给你一个nm的地图 这个地图中有三种格式
第一种 '’ 代表这个地方可以使用魔法跳转到另一个地方（后面告诉）。
第二种 ‘0’~‘9’
代表这个地方可以得到的矿石数量。
第三种 ‘#’
代表这个地方是墙 不能通过。
然后再给你每一个’*'可以跳转到的地方 从左到右 从上到下 一次给出
起点为 左上角 每一个方格 可以向下或者向右走
然后让你求 这个地图中 最多能得到多少矿石（起点为左上角，终点任意）（魔法可以无限次用 但是 每个方格的矿石只能得到一次）
输出这个答案。
我的做法：
spfa+缩点 缩点可以用tarjan强连通算法。
如果可以施展魔法跳到另一个的地方之后。 如果能从那个地方再回到这个地方。那么所有这条路径上的点权都可以缩为1点。它形成了一个环 可以通过tarjan求出强连通分量 然后以这些强连通分量建图跑一遍spfa就可以得出答案。。详情代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
char map1[50][50];
int map2[50][50];
int val[2500];
int dis[2500];
struct point {
int x,y,tx,ty;
}cs[2500];
#define MAXN 2500
vector <int> e1[MAXN];
vector <int> e[MAXN];
int dfn[MAXN],low[MAXN],stack[MAXN],bleg[MAXN];
int top,times,tot;
void tarjan_x(int u){
dfn[u]=low[u]=++times;
stack[++top]=u;
for(int i=0;i<(int)e[u].size();i++){
int v=e[u][i];
if(!dfn[v]){
tarjan_x(v);
low[u]=min(low[u],low[v]);
}
else if(!bleg[v])
low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u]){
bleg[0]++;
do{
bleg[stack[top]]=bleg[0];
}while(stack[top--]!=u);
}
}
void init(){
memset(dfn,0,sizeof(dfn));
memset(bleg,0,sizeof(bleg));
top=times=0;
}
void tarjan(){
init();
for(int i=1;i<=tot;i++)
if(!dfn[i])tarjan_x(i);
}
int bfs(){
queue <int> q;
q.push(bleg[1]);
memset(dis,0,sizeof(dis));
dis[bleg[1]]=val[bleg[1]];
int mm=0;
while(!q.empty()){
int now=q.front();
q.pop();
if((mm<dis[now]))mm=dis[now];
for(int i=0;i<(int)e1[now].size();i++){
int next=e1[now][i];
if(dis[now]+val[next]>dis[next]){
dis[next]=dis[now]+val[next];
q.push(next);
}
}
}
return mm;
}
int main()
{
int t,cas=0;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<MAXN;i++)e[i].clear();
for(int i=0;i<MAXN;i++)e1[i].clear();
memset(val,0,sizeof(val));
int tt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf(" %c",&map1[i][j]);
if (map1[i][j]=='#') {
map2[i][j]=-1;
}
else if(map1[i][j]=='*'){
map2[i][j]=0;
cs[tt].x=i;
cs[tt].y=j;
++tt;
}
else {
map2[i][j]=map1[i][j]-'0';
}
}
}
for(int i=0;i<tt;i++){
scanf("%d%d",&cs[i].tx,&cs[i].ty);
}
for(int i=0;i<tt;i++){
int now=cs[i].x*m+cs[i].y+1;
int next=cs[i].tx*m+cs[i].ty+1;
e[now].push_back(next);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(map2[i][j]==-1){ continue; }
int now=i*m+j+1;
if(i+1<n&&map2[i+1][j]!=-1){
int next=(i+1)*m+j+1;
e[now].push_back(next);
}
if(j+1<m&&map2[i][j+1]!=-1){
int next=i*m+j+1+1;
e[now].push_back(next);
}
}
}
tot=n*m;
tarjan();
for(int i=1;i<=tot;i++){
val[bleg[i]]+=map2[(i-1)/m][(i-1)%m];
for(int j=0;j<(int)e[i].size();j++){
int v=e[i][j];
if(bleg[i]!=bleg[v]){
e1[bleg[i]].push_back(bleg[v]);
}
}
}
printf("%d\n",bfs());
}
return 0;
}
|
