【日常学习】【强连通分量tarjan缩点】codevs1611 抢掠计划题解

矫情吗；* 2022-08-09 09:14 150阅读 0赞

题目描述 Description

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，  
在每个路口都设立了一个Siruseri 银行的ATM 取款机。令人奇怪的是，Siruseri  
的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。  
Banditji 计划实施Siruseri 有史以来最惊天动地的ATM 抢劫。他将从市中心  
出发，沿着单向道路行驶，抢劫所有他途径的ATM 机，最终他将在一个酒吧庆  
祝他的胜利。  
使用高超的黑客技术，他获知了每个ATM 机中可以掠取的现金数额。他希  
望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可  
以经过同一路口或道路任意多次。但只要他抢劫过某个ATM 机后，该ATM 机  
里面就不会再有钱了。  
例如，假设该城中有6 个路口，道路的连接情况如下图所示：  
市中心在路口1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表  
示。每个ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢  
劫的现金总数为47，实施的抢劫路线是：1-2-4-1-2-3-5。

![1611.jpg][]

输入描述 Input Description

第一行包含两个整数N、M。N 表示路口的个数，M 表示道路条数。接下来  
M 行，每行两个整数，这两个整数都在1 到N 之间，第i+1 行的两个整数表示第  
i 条道路的起点和终点的路口编号。接下来N 行，每行一个整数，按顺序表示每  
个路口处的ATM 机中的钱数。接下来一行包含两个整数S、P，S 表示市中心的  
编号，也就是出发的路口。P 表示酒吧数目。接下来的一行中有P 个整数，表示  
P 个有酒吧的路口的编号。

输出描述 Output Description

输出一个整数，表示Banditji 从市中心开始到某个酒吧结束所能抢劫的最多  
的现金总数。

样例输入 Sample Input

6 7  
1 2  
2 3  
3 5  
2 4  
4 1  
2 6  
6 5  
10  
12  
8  
16  
1 5  
1 4  
4 3 5 6

样例输出 Sample Output

数据范围及提示 Data Size & Hint

50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM  
机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心  
沿着Siruseri 的单向的道路到达其中的至少一个酒吧。

第一次写tarjan 承蒙BYVoid前辈和里奥神犇帮助。

本博文和代码主要参考了**[BYVoid前辈博文][BYVoid]以及[里奥神犇博文（非递归版本）][Link 1]**

关于tarjan具体的做法，上面的博文中都有详细的介绍，在这里简要总结一下流程：

1.开始就是做一个深搜，当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。  
2.每搜索到一个点，将它压入栈顶。  
3.当点p有与点p’相连时，如果此时（时间为dfn\[p\]时）p’不在栈中，p的low值为两点的low值中较小的一个。  
4.当点p有与点p’相连时，如果此时（时间为dfn\[p\]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个。  
5.每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。  
6.继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。

由于每个顶点只访问过一次，每条边也只访问过一次，我们就可以在O（n+m）的时间内求出有向图的强连通分量。

对于这道题目，做完缩点，之后把每个强连通分量（英文缩写SCC）当成一个点，用vector重新建图，然后跑单源最长路即可

我们先放上递归版本的代码吧：

//codevs1611 ÇÀÂÓ¼Æ»® Ç¿Á¬Í¨TarjanËõµã
    //copyright by ametake
    //Cheer up !!!
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    #include
           
             using namespace std; const int maxn=500000+10; int n,m; int S,P; int head[maxn],to[maxn<<2],next[maxn<<2],et=0; int money[maxn]; bool inq[maxn],ins[maxn]; int dfn[maxn],low[maxn],sta[maxn],stp=0,tot=0;//stp is the point of stack ans tot is the number of the strongly connected components int inwhich[maxn],scc[maxn];//in which scc and the scc contains how much money int dis[maxn],dep; vector
            
              g[maxn]; queue
             
               q; inline void add(int &x,int &y) { et++; to[et]=y; next[et]=head[x]; head[x]=et; } inline int read() { int a=0,b=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') b=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } a*=b; return a; } void init() { n=read(); m=read(); int x,y; for (int i=0;i
              
               dis[g[now][i]]) { dis[g[now][i]]=dis[now]+scc[g[now][i]]; if (!inq[g[now][i]]) { q.push(g[now][i]); inq[g[now][i]]=true; } } } } int now,ans=0; for (int i=1;i<=P;i++) { now=read(); //printf("%d %d\n",now,dis[inwhich[now]]); if (dis[inwhich[now]]>ans) ans=dis[inwhich[now]]; } printf("%d\n",ans); } int main() { freopen("1.txt","r",stdin); freopen("2.txt","w",stdout); init(); for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); //for (int i=1;i<=n;i++) printf("%d\n",inwhich[i]); /* for (int i=1;i<=tot;i++) { printf("%d.%d\n",i,scc[i]); } */ for (int i=1;i<=n;i++) { for (int j=head[i];j!=0;j=next[j]) { if (inwhich[to[j]]!=inwhich[i]) { g[inwhich[i]].push_back(inwhich[to[j]]);//now there's no single point,every point is in a scc } } } spfa(inwhich[S]); return 0; }

关于递归版本代码我还存有一些疑问，或者说想法。我们来看这样一段代码：

else if (ins[to[t]])
            {
                low[x]=min(low[x],dfn[to[t]]);
            }

代码意思很简单，如果这个点已经在栈中，也就是已经找到了当前点的祖先，发现一条后向边，说明有环，那么此时当前节点的low值应当是自身low值和这个祖先点的dfn中较小的一个。

然而对这样一张图：

![SouthEast][]

我们模拟一下tarjan的过程，是这样的：

![SouthEast 1][]、

搜索的顺序是①->②->③->④

得到最原始的dfn和low如图

接下来

![SouthEast 2][]

![SouthEast 3][]

![SouthEast 4][]

因此，最终遍历的结果是：

![SouthEast 5][]

我们发现，23456五个点是一个强连通分量，最终也同时出栈。

但是，**同一个强连通分量中的点的low值并不相同**

这是可以理解的，因为low的定义是：该节点所能达到的dfn最小的点的dfn值，而对于节点5，其所能达到的最小dfn就是dfn\[6\]=4

既然这样，为什么不能在发现当前节点的下一个点在栈中时，把low\[now\]赋值为low\[now\]和下一个节点的low的最小值呢？

这是我的疑问，如果幸蒙哪位大神屈尊赐教，鄙人不胜感激啊···

然而这道题目由于有五十万的数据规模，递归版会爆栈。因此我们不得不采用非递归版本

非递归版本相当于使用手写栈模拟系统栈，以空间换时间（这句话说的其实不对，因为系统栈一样占空间，实际空间并没有增多。只不过由于系统栈限制为2M，而我们自己开空间有128-2=126M可以用，因此我们手动把原来在系统栈空间中的栈转移到我们自己使用的空间内）。

我们先来放上代码，根据代码来解释非递归的过程：

//codevs1611 ÇÀÂÓ¼Æ»® Ç¿Á¬Í¨TarjanËõµã
    //copyright by ametake
    //Cheer up !!!
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    #include
           
             #include
            
              using namespace std; const int maxn=500000+10; int n,m; int S,P; int head[maxn],to[maxn<<2],next[maxn<<2],et=0; int money[maxn]; bool inq[maxn],ins[maxn]; int dfn[maxn],low[maxn],sta[maxn],stp=0,tot=0;//stp is the point of stack ans tot is the number of the strongly connected components int inwhich[maxn],scc[maxn];//in which scc and the scc contains how much money int dis[maxn],dep; vector
             
               g[maxn]; queue
              
                q; stack
               
                 big; inline void add(int &x,int &y) { et++; to[et]=y; next[et]=head[x]; head[x]=et; } inline int read() { int a=0,b=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') b=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } a*=b; return a; } void init() { n=read(); m=read(); int x,y; for (int i=0;i
                
                 dfn[now]) low[now]=min(low[now],low[to[i]]); else if (ins[to[i]]) low[now]=min(low[now],dfn[to[i]]); } if (dfn[now]==low[now]) { tot++; int j; do { j=sta[stp--]; ins[j]=false; inwhich[j]=tot; scc[tot]+=money[j]; }while (j!=now); } big.pop(); } } } void spfa(int s)//443412 { inq[s]=true; q.push(s); dis[s]=scc[s]; while (!q.empty()) { int now=q.front(); q.pop(); inq[now]=false; for (int i=0;i
                 
                  dis[g[now][i]]) { dis[g[now][i]]=dis[now]+scc[g[now][i]]; if (!inq[g[now][i]]) { q.push(g[now][i]); inq[g[now][i]]=true; } } } } int now,ans=0; for (int i=1;i<=P;i++) { now=read(); //printf("%d %d\n",now,dis[inwhich[now]]); if (dis[inwhich[now]]>ans) ans=dis[inwhich[now]]; } printf("%d\n",ans); } int main() { freopen("1.txt","r",stdin); freopen("2.txt","w",stdout); init(); for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); //for (int i=1;i<=n;i++) printf("%d\n",inwhich[i]); /* for (int i=1;i<=tot;i++) { printf("%d.%d\n",i,scc[i]); } */ for (int i=1;i<=n;i++) { for (int j=head[i];j!=0;j=next[j]) { if (inwhich[to[j]]!=inwhich[i]) { g[inwhich[i]].push_back(inwhich[to[j]]);//now there's no single point,every point is in a scc } } } spfa(inwhich[S]); return 0; }

非递归版本其实就是模拟递归，但由于无法进行递归，递归返回值需要我们通过循环自己去求。

递归的具体流程操作是这样的：

1.首先，从源点开始深搜。如果找到的是祖先会跳过继续找下去，直到找不到可行点才考虑祖先。最后进入下一段程序时一定是没有路了或者找到祖先了。

while循环实际模拟了深搜，因为如果能搜，就会一直搜到新节点并压栈，不会出现big.top()==now即当前正在搜的节点为栈顶的情况

如果出现了big.top()==now的情况，只会是两种情况：当前节点没有可以搜的出边了（可能真的没有边，也可能边都已经搜过了），或者找到了已经在栈中的节点。

无论是哪种情况，我们都进入第二步。

为什么我们只进行单路径深搜，一条路走到黑而不注意同一个点连接的其他子节点呢？别急，因为递归tarjan本身就是一个深搜并回溯的过程。我们一条路搜下去，搜到头，退栈或不退栈，结束后由于上面while队伍不为空的限制，会再次进行循环。而这一次，因为已经搜过的点dfn已经有值了，就不会再搜了。这个过程就是深搜回溯的过程。

2.现在，由于程序已经进入了第二阶段，一定是没有路了或者跳过了祖先。

无论是哪种情况，这个节点的向下搜索的子树一定已经遍历完毕了，因为如果没有遍历完毕在第一步中会继续搜下去。

我们先处理祖先的情况：

如果有一条路通向该节点的祖先，那么在第一步中这个祖先被跳过了，因此为了找到祖先我们再对所有出边进行一次循环。此时如果遇到祖先，更新当前节点的low值；如果遇到子节点，有可能子节点通向更早的祖先，low值比当前节点还小，因此更新当前节点low值。

如果是没有路了，那么循环无法执行，此时会直接退栈。

3.这一步处理完毕后，当前节点已经完全处理完毕，弹出大栈（相当于递归结束，得到的值将用于返回处理更早的节点）。但是在小栈中不一定弹出，要等找到强连通分量的根才会集中弹出。

至此，非递归tarjan的基本流程就解说完毕了。

另外要注意，尽管是单向边，也有可能两点之间有正反两条边这样的，邻接表数组还是要开两倍

谢谢阅读，今天花了一天时间终于搞定了tarjan，想Robert Tarjan老先生鞠个躬，今晚可要好好练习了。

——大行不顾细谨，大礼不辞小让。

[1611.jpg]: http://codevs.cn/media/image/1611.jpg
[BYVoid]: https://www.byvoid.com/blog/scc-tarjan
[Link 1]: http://blog.csdn.net/t14t41t/article/details/49103303
[SouthEast]: /images/20220731/9660b9e187734f919014b1e3f17e4968.png
[SouthEast 1]: /images/20220731/d3b8bd4d08f643e6a1540c5627cb3fde.png
[SouthEast 2]: /images/20220731/2a7119270da24770b43f5529b1ef3344.png
[SouthEast 3]: /images/20220731/11e5a9cf4c34427c9419808f1fa88cba.png
[SouthEast 4]: /images/20220731/389d6c13851e4cf7af0be1252ae2749d.png
[SouthEast 5]: /images/20220731/d6fa1ffc65b9407f8e3f1ed5e6da37ca.png