题解：P3387 【模板】缩点

· · 题解

题解优势： 本身作者的水平有限，所以语言会相对通俗。

一些概念

  1. 强连通分量：\ 若一个有向图 G，各个点之间互相连通，我们则称图 G 是强连通的；强连通分量就是指一个强连通的子图。
  2. 缩点是什么：\ 缩点用于将有向图的强连通分量缩成一个结点，并构造一个新的有向无环图。这个新的图中的每个结点代表原图的一个强连通分量。

下图就是一个缩点的示例。

为什么要用缩点

通过缩点算法，可以将有向图中的强连通分量收缩为单个节点，从而将原图转化为一个有向无环图，这使得图的结构更简单（无环），更容易进行后续的处理和优化。

回到这道题，根据强连通分量的定义，强连通分量内的点互相连通，所以如果走到强连通分量中的一个点，那么走完整个强连通分量就是最优的。

怎么缩点

Tarjan

使用 Tarjan 算法找出强连通分量。

前情提要：

我们在 Tarjan 的过程中会维护三个数组 dfn、low 和 vis、一个变量 times、一个栈。

接下来，使用 dfs 遍历整个图。

每到一个点都会先将当前点压入栈中，更新 vis_i，并将 dfn_i 和 vis_i 更新为自增后的 times。

若下一个将要遍历到的点不是上一个点（不走回头路），先将当前的那么考虑：

  1. 若下一个点未被访问过，即 if(!dfn[v])，那么继续访问，并在回来的时候更新 low。
  2. 若下一个点被访问过了。
    • 下个点在不栈中，那么就是已经访问完了，不用理他。
    • 下一个点还在栈中，更新 low。

Tarjan 正确性证明

证明：从 u 出发的 DFS 全部结束回到 u 时，若 dfn[u] == low[u], 此时将栈中 u 及其上方的节点弹出，就找到了一个强连通分量？

我们可以将其拆为两部分进行证明。

  1. 为什么 DFS 生成树中的强连通分量必然连续

证明

假设节点 u 是一个强连通分量的根，并且存在节点 v 与 u 同属于强连通分量但不在 u 的子树中。由于强连通分量内节点互相可达，v 到 u 的路径必然存在。根据 DFS 的性质：

  • 若 v 在 u 之前被访问：u 应在 v 的子树中被访问，与 u 是根矛盾。

  • 若 v 在 u 之后被访问：u 到 v 的路径会使 v 在 u 的子树中。

所以我们可以直接将栈中 u 及其上方的节点弹出得到一个强连通分量。

  1. 为什么当 dfn[u] == low[u] 时弹出栈的节点能构成一个强连通分量

证明

low[u] == dfn[u] 说明 u 无法到达更早的祖先节点。栈中位于 u 之上的节点 w 均满足：

dfn_u \le low_w \le dfn_w

这表明 w 只能到达 u 或 u 的子孙节点，即所有 w 与 u 互相可达。

若 u 是一个强连通分量的根，根据两个数组的定义，则它的 low 和 dfn 必定，不会被更新，保持为初始的 low[u]=dfn[u]=++times，其子孙节点最多只能回溯到 u，故当 low[n] == dfn[n] 时，n 必定为一个强连通分量的根。

缩点

缩点，将每一个强连通分量缩为一个权值为强连通分量内点的权值总合的点并构造一个新的图。

以一个例子来演示一下。

6 7
5 3 8 2 4 5
1 2
2 3
3 4
4 5 
5 3
2 6
6 2

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k=0,ans=0,d[100010],vis[100010],dp[100010],head1[100010],head2[100010],times=0,dfn[100010],low[100010],w[100010],sccw[100010],id[100010],cnt=0;
stack<int>s;
queue<int>q;
struct Edge
{
    int u,v,next;
}edg[200010];
void addedge(int u,int v,int head[])
{
    edg[++k].u=u;
    edg[k].v=v;
    edg[k].next=head[u];
    head[u]=k;
} 
void dfs(int x)
{
    s.push(x);
    vis[x]=1;
    dfn[x]=low[x]=++times;
    for(int i=head1[x];i!=0;i=edg[i].next)
    {
        int v=edg[i].v;
        if(!dfn[v])
        {
            dfs(v);
            low[x]=min(low[x],low[v]);
        }
        else if(vis[v])low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x])
    {
        cnt++;
        int t;
        do
        {
            t=s.top();
            s.pop();
            vis[t]=0;
            sccw[cnt]+=w[t];
            id[t]=cnt;
        }while(t!=x);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1,u,v;i<=m;i++)
    {
        cin>>u>>v;
        addedge(u,v,head1);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
    for(int i=1,u,v;i<=m;i++)
    {
        u=id[edg[i].u],v=id[edg[i].v];
        if(u!=v)
        {
            addedge(u,v,head2);
            d[v]++;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        dp[i]=sccw[i];
        if(!d[i])q.push(i);
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=head2[t];i!=0;i=edg[i].next)
        {
            int v=edg[i].v;
            dp[v]=max(dp[v],dp[t]+sccw[v]);
            d[v]--;
            if(!d[v])q.push(v);
        }
    }
    for(int i=1;i<=cnt;i++)ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}