POJ 3592 强连通缩点+spfa最长路

题意：

给定n*m的地图 (从(0,0) 开始)

#代表墙，*代表传送门（能传送到的坐标在下面依次给出），数字代表宝藏数（每次经过能且仅能取走一块宝藏）

起点在(0,0), 终点任意，且每次只能↓或→，或者传送

问：

最多能拿到多少块宝藏

思路：因为能传送，所以会出现环形路径，那么我们把能构成的环形路径的点缩点得到一个点，并把该点权值设为 环形路径内所有的点权和。

对于缩点后的图，我们把每个点权值设为父边的边权

这样跑一次spfa 最长路，最远点距离就是答案。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        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
       
         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
        
         G[N]; int dis[N], D[N][N]; int spfa(){ memset(a, 0, sizeof(a)); memset(dis, -1, sizeof(dis)); queue
         
          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