P3387 缩点 • CoderXL's Blog

先从简单的情形入手。

有向无环图#

假如题目的图是有向无环图（DAG），那么如何求解？

朴素方法是：从每个节点出发进行 DFS，枚举所有的路径，然后选出经过的权值和最大的。
时间复杂度是 $O(\text{路径总数})$ ，非常大。

稍作思考可得：最优解一定始于图上入度为零的点，终于出度为零的点。

为什么 DAG 上的解的路径一定是从入度为零的点到出度为零的点？

那么根据拓扑排序（见本周每日一题 ↗）的知识，图中一定存在入度为零（ $d^-=0$ ）的点和出度为零（ $d^+=0$ ）的点。

而考虑任何候选的路径，如果该路径的起点的 $d^->0$ ，那么可以把该路径向前延伸到某个指向起点的节点，由于题目保证了节点权值的非负性，因此这样的延伸一定不会更劣；同理如果终点 $d^+>0$ ，也可以这样延伸。

这就证明了，最终的解一定以 $d^-=0$ 的点为起点，以 $d^+=0$ 的点为终点。

因此改进的方法是：依次以所有入度为零的点为起点进行 DFS。这样的时间复杂度正比于图上所有“长路径”的条数，如果设 DFS 的平均深度为 $L$ （Layer），那么时间复杂度约为 $O(\left({E \over V}\right)^L)$ .

但是，借助拓扑排序的经验，我们知道 DAG 有两个非常好的性质：最优子结构和无后效性。

也就是说，如果一个节点的所有前序节点已经求解好了，我们就可以使用 DP 的方式转移状态，轻松延伸路径。

反过来，我们可以延迟访问节点，并在节点处维护当前最优解的信息，直到其所有前序节点已经被求解好，此时再进行处理，就能避免重复访问，将时间复杂度降到 $O(V+E)$ .

因此这个问题本质上可以在拓扑排序的过程中解决。

下面这张图展示了拓扑排序相比 DFS 省去的重复访问。

flowchart LR

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

1 --> 4 --> 7
1 --> 5 --> 7
1 --> 6 --> 7

2 --> 4 --> 8
2 --> 5 --> 8
2 --> 6 --> 8

3 --> 4
3 --> 5
3 --> 6

DFS 需要遍历所有长路径，遍历次数接近 $O(\left({E \over V}\right)^L)$

flowchart LR

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

1 --> 4 ~~~ 7
1 --> 5 ~~~ 7
1 --> 6 ~~~ 7

2 --> 4 ~~~ 8
2 --> 5 ~~~ 8
2 --> 6 ~~~ 8

3 --> 4
3 --> 5
3 --> 6

classDef invisibleNode opacity:0;
class 7,8 invisibleNode;

flowchart LR

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

1 ~~~ 4 --> 7
1 ~~~ 5 --> 7
1 ~~~ 6 --> 7

2 ~~~ 4 --> 8
2 ~~~ 5 --> 8

2 ~~~ 6 --> 8
3 ~~~ 4
3 ~~~ 5
3 ~~~ 6

classDef invisibleNode opacity:0;
class 1,2,3 invisibleNode;

拓扑排序按“层”拆分，把遍历次数降到 $O(V+E)$

考虑环#

但是一般的有向图可能存在环。

分析一下发现：如果候选路径经过环上的部分点，但没有包含整个环，那么可以把整个环都加入进来，答案不会变得更劣。
这是因为题目允许重复经过节点，且不会重复计入权重。

更进一步，环可能互相嵌套形成更加复杂的结构。但这些结构的共同点都是：任何节点之间互相可达。我们称之为“强连通分量”。

缩点#

由前面的分析可知，这些处于同一个强连通分量中的节点，在最优解路径中，要么全部被选中，要么一个也不选。这使得它们对外表现为的一个统一的整体。

这启发我们考虑把整个强连通分量用单个节点代替，新节点的权重就是该强连通分量中所有节点的权重之和，而它和图上其它节点的连接关系就自然继承了。
这个过程被形象地称为“缩点”。

flowchart LR

1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))
8((8))
9((9))

7 --> 9
9 --> 4
8 --> 9
3 --> 4
3 --> 6
6 --> 2
2 --> 4
4 --> 5
2 --> 3
5 --> 6
1 --> 2

linkStyle 3,4,5,6,7,8,9 stroke:red,stroke-width:1px;
classDef sscNode fill:pink;
class 2,3,4,5,6 sscNode

标红的节点和边属于同一个强连通分量
可以验证一下它们是否两两可达

flowchart LR

1((1))
2((2))
7((7))
8((8))
9((9))

1 --> 2
7 --> 9
9 --> 2
8 --> 9

classDef sscNode fill:pink;
class 2 sscNode

缩点之后，外部节点与强连通分量的连接关系被继承

算法#

Tarjan 算法是求强连通分量的经典算法，它借助 DFS 搜索树（亦称 DFS 生成树）的结构判断环是否存在。

流程#

维护两个数组：

dfn[u]：节点 $u$ 在 DFS 中的访问时间戳（第几个被访问的）
low[u]：节点 $u$ 通过其子树中的回边能到达的最早的祖先的 dfn 值

然后从某个未访问的顶点开始 DFS，维护一个全局时间戳 timer 和一个栈：

进入顶点 $u$ 时，设 dfn[u] = low[u] = ++timer，并将 $u$ 压入栈
对 $u$ $u$ 的每个邻居 $v$ $v$ ：
- 如果 $v$ 未访问，递归 DFS( $v$ )，回溯后 low[u] = min(low[u], low[v])
- 如果 $v$ 已在栈中，说明这条边是“回边”，和 DFS 树上的祖先构成一个环，此时令low[u] = min(low[u], dfn[v])
当 low[u] == dfn[u] 时，说明 $u$ 是一个强连通分量的根，此时从栈中不断弹出顶点直到弹出 $u$ ，这些顶点构成一个（极大的）强连通分量。（一个顶点自身也可算作一个强连通分量）

限于篇幅，算法的深入理解和正确性证明推荐移步题解：P3387 【模板】缩点 ↗，图上算法#Tarjan 求强连通分量 ↗，强连通分量 - OI Wiki ↗。

而对于这道题，形象地说，我们需要把处于同一个强连通分量中的点“染成同一个颜色”，然后使用颜色代替原来的顶点编号重新建图，这个新的图一定是一个 DAG.

代码#

求解强连通分量的同时进行染色，然后重建为 DAG，最后进行拓扑排序。

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Node
{
    int a;
    int dfn;
    int low;
    int c;
}node[10010],node1[10010];
int s[10010];
int top;
int dp[10010];
struct Edge
{
    int to;
    int next;
}edge[100010],edge1[100010];
int in[10010];
int head[10010],cnt,head1[10010],cnt1;
int curr;
int color;
int q[10010],h=1,t;
bool flag[10010];
int ans;
void add(int x,int y)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
void add1(int x,int y)
{
    cnt1++;
    edge1[cnt1].to=y;
    edge1[cnt1].next=head1[x];
    head1[x]=cnt1;
}
void dfs(int x)
{
    curr++;
    node[x].dfn=curr;
    node[x].low=curr;
    top++;
    s[top]=x;
    flag[x]=true;
    for(int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if(!node[y].dfn)
        {
            dfs(y);
            node[x].low=min(node[x].low,node[y].low);
        }
        else
        {
            if(flag[y])
            {
                node[x].low=min(node[x].low,node[y].dfn);
            }
        }
    }
    if(node[x].low==node[x].dfn)
    {
        color++;
        while(s[top]!=x)
        {
            node[s[top]].c=color;
            flag[s[top]]=false;
            top--;
        }
        node[s[top]].c=color;
        flag[s[top]]=false;
        top--;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>node[i].a;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!node[i].dfn)
        {
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        node1[node[i].c].a+=node[i].a;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j;j=edge[j].next)
        {
            int y=edge[j].to;
            if(node[i].c==node[y].c)
                continue;
            add1(node[i].c,node[y].c);
            in[node[y].c]++;
        }
    }
    for(int i=1;i<=color;i++)
    {
        if(in[i]==0)
        {
            t++;
            q[t]=i;
            flag[i]=true;
        }
        dp[i]=node1[i].a;
    }
    while(h<=t)
    {
        int x=q[h];
        flag[x]=false;
        h++;
        for(int i=head1[x];i;i=edge1[i].next)
        {
            int y=edge1[i].to;
            if(!flag[y])
            {
                t++;
                q[t]=y;
                flag[y]=true;
            }
            dp[y]=max(dp[y],dp[x]+node1[y].a);
        }
    }
    for(int i=1;i<=color;i++)
    {
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

cpp