强连通分量

 题意：一个n行m列的矩阵图，上面有3种点，可能是数字x(0<=x<=9)，表示这里有多少个矿石，#表示不能走到这点，*表示传送点，对应一个目标点，可以瞬间传送到目标点。你从（0,0）左上角处出发，行走的方向只能是向左或者向下，要求你走到某个地方（不一定是右下角），让你得到的矿石最多。一个地方的矿石只能采集一次，下次再去到那个点是没有矿石的。注意几点，传送点可能将你传送到#这种点，那么相当于这个传送点是多余的等于没用，另外在传送点可以选择传送或者不传送继续走。

 

分析：由于传送点的存在，可能使这个有向图构成环，进而可能产生强连通分量，所以先建图，进行一次强连通分量缩点，为什么缩点，因为易知，在一个强连通分量内的点都是可以全部到达的，所以这个点内的矿石都能采集到。缩点后得到一个DAG，对这个DAG重新建图，另外重新计算缩点后每个点有多少矿石（即原来小点的矿石和）。然后从点(0,0)缩点后所在那个大点出发，用BFS搜索，求一次最长路，再取最大值即可

 

总体来说这题不难，代码量，对于图论的题来讲，也差不多是这么多了，写的时候状态不好，很多小bug，调试很久wa了好几次才过。

这题总的来说也不算难，就Tarjan缩点+bfs搜索最长路

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 2100char a[50][50];vector
            
             mp;vector
             
              e[N];vector
              
               ver[N];stack
               
                sta;queue
                
                 que;int row,col,n;int dfn[N],low[N],belong[N],dcnt,bcnt;int val[N],sv[N],d[N];bool ins[N],inq[N];void input(){ cin >> row >> col; n = row * col; for(int i=0; i
                 
                  > a[r]; for(int r=0; r
                  
                   = '0' && a[r][c] <= '9') val[u] = a[r][c] - '0'; else { val[u] = 0; cin >> x >> y; if(a[x][y] != '#') { v = x * col + y; e[u].push_back(v); } } }}void rebuild(){ for(int i=1; i<=bcnt; i++) ver[i].clear(); for(int i=0; i
                   
                    > cas; while(cas--) { input(); Tarjan(); rebuild(); bfs(); int res = 0; for(int i=1; i<=bcnt; i++) res = max(res , d[i]); cout << res << endl; } return 0;}