题意:
给定n*m的地图 (从(0,0) 开始)
#代表墙,*代表传送门(能传送到的坐标在下面依次给出),数字代表宝藏数(每次经过能且仅能取走一块宝藏)
起点在(0,0), 终点任意,且每次只能↓或→,或者传送
问:
最多能拿到多少块宝藏
思路:因为能传送,所以会出现环形路径,那么我们把能构成的环形路径的点缩点得到一个点,并把该点权值设为 环形路径内所有的点权和。
对于缩点后的图,我们把每个点权值设为父边的边权
这样跑一次spfa 最长路,最远点距离就是答案。
#include<stdio.h> #include<string.h> #include<iostream> #include<vector> #include<queue> using namespace std; #define N 1700 //N为点数 #define M 10000 //M为边数 int n, m, a[N], val[N]; int idx(int x, int y){return x*m+y;} char map[N][N]; struct Edge{ int from, to, nex; bool sign;//是否为桥 }edge[M<<1]; int head[N], edgenum; void add(int u, int v){ Edge E={u, v, head[u], false}; edge[edgenum] = E; head[u] = edgenum++; } int DFN[N], Low[N], Stack[N], top, Time; int taj;//连通分支标号,从1开始 int Belong[N];//Belong[i] 表示i点属于的连通分支 bool Instack[N]; vector<int> bcc[N]; //标号从1开始 void tarjan(int u ,int fa){ DFN[u] = Low[u] = ++ Time ; Stack[top ++ ] = u ; Instack[u] = 1 ; for (int i = head[u] ; i!=-1 ; i = edge[i].nex ){ int v = edge[i].to ; if(DFN[v] == -1) { tarjan(v , u) ; Low[u] = min(Low[u] ,Low[v]) ; if(DFN[u] < Low[v]) { edge[i].sign = 1;//为割桥 } } else if(Instack[v]){ Low[u] = min(Low[u] ,DFN[v]) ; } } if(Low[u] == DFN[u]){ int now ; taj ++ ; bcc[taj].clear(); do{ now = Stack[-- top] ; Instack[now] = 0 ; Belong [now] = taj ; bcc[taj].push_back(now); }while(now != u) ; } } void tarjan_init(int all){ memset(DFN, -1, sizeof(DFN)); memset(Instack, 0, sizeof(Instack)); top = Time = taj = 0; for(int i=0;i<all;i++)if(DFN[i]==-1 && map[i/m][i%m] != ‘#‘)tarjan(i, i); //点标从0开始 } vector<int>G[N]; int dis[N], D[N][N]; int spfa(){ memset(a, 0, sizeof(a)); memset(dis, -1, sizeof(dis)); queue<int>q; q.push(Belong[0]); int ans = val[Belong[0]]; dis[Belong[0]] = ans; while(!q.empty()){ int u = q.front(); q.pop(); a[u] = 0; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(dis[v] < dis[u] + D[u][v]) { dis[v] = dis[u] + D[u][v]; ans = max(ans, dis[v]); if(a[v] == 0)q.push(v), a[v] = 1; } } } return max(ans, 0); } int main(){ int u, v, i, j, T;scanf("%d",&T); while(T--){ scanf("%d %d", &n, &m); memset(head, -1, sizeof(head)); edgenum = 0; memset(a, 0, sizeof(a)); memset(val, 0, sizeof(val)); for(i = 0; i < n; i++) scanf("%s",map[i]); for(i = 0; i < n; i++) { for(j = 0; j < m; j++)if(map[i][j] != ‘#‘) { if(i<n-1 && map[i+1][j] != ‘#‘)add(idx(i,j), idx(i+1,j)); if(j<m-1 && map[i][j+1] != ‘#‘)add(idx(i,j), idx(i,j+1)); if(map[i][j] == ‘*‘) {scanf("%d %d", &u, &v); if(map[u][v]==‘#‘)continue;add(idx(i,j), idx(u,v));} else a[idx(i,j)] = map[i][j]-‘0‘; } } tarjan_init(n*m); for(i = 1; i <= taj; i++)for(j = 0; j < bcc[i].size(); j++)val[i] += a[bcc[i][j]]; for(i = 1; i <= taj; i++)G[i].clear(); for(i = 0; i < edgenum; i++){ u = Belong[edge[i].from]; v = Belong[edge[i].to]; if(u != v) G[u].push_back(v),D[u][v] = val[v]; } printf("%d\n", spfa()); } return 0; } /* 99 2 2 11 1* 0 0 3 3 11# 1*1 ##9 0 0 99 10 10 1167811678 1*77811678 1*70001678 1*77811678 1#77800078 1#77837### 1*00037### 1*34000### 1*3451*778 37###1#345 5 5 5 5 5 6 5 7 5 8 5 9 5 10 */