题解 P4742 【[Wind Festival]Running In The Sky】

STrAduts · 2021-01-04 13:21:40 · 题解

引子

果然老师们都只看标签拉题。。。

发现需要处理环，然后通过一些神奇的渠道了解到有个东西叫缩点。

紧接着搜了一下缩点，发现了 Tarjan 算法。

然后又翻了翻算法竞赛，于是一去不复返……

一些定义

给定一张有向图。对于图中任意两个节点 x, y，存在从 x 到 y 的路径，也存在 y 到 x 的路径。则称该有向图为“强连通图”。

有向图的强连通子图被称为强连通分量 SCC (Strongly Connected Component)。

显然，环一定是强连通图。因为如果在有向图中存在 x 到 y 的路径，且存在 y 到 x 的路径，那么 x, y 一定在同一个环中。

对于一个有向图，如果从 root 可以到达图中所有的点，则称其为“流图”，而 root 为流图的源点。

以 root 为原点对流图深度优先遍历，每个点只访问一次，在过程中，所有发生递归的边 (x, y) 构成的一棵树叫做这个流图的搜索树。

在深度优先遍历时，对每个访问到的节点分别进行整数 1...n 标记，该标记被称为时间戳，记为 dfn[x]。

流图中的每条有向边 (x, y) 必然是以下四种中的一种：

1. 前向边，指搜索树中 x 是 y 的祖先节点

2. 后向边，指搜索树中 y 是 x 的祖先节点

3. 树枝边，指搜索树里的边，满足 x 是 y 的父节点。

4. 其他边（好像也叫横叉边），指除了上面三种情况的边。且一定满足 dfn[y] < dfn[x]

Tarjan算法之强连通分量

Tarjan 算法基于有向图的深度优先遍历，能够在线性时间中求出一张有向图的各个强连通分量。

其核心思想就是考虑两点之间是否存在路径可以实现往返。

我们在后文中，都会结合搜索树（本身就是深度优先遍历的产物）来考虑，这样就可以在深度优先遍历的同时完成我们的目标。

对于流图，前向边作用不大，因为当前搜索树中一定存在 x 到 y 的路径。

后向边就很重要了，因为它一定可以和搜索树中 x 到 y 的路径组成环。

横叉边需要判断一下，如果这条横叉边能到达搜索树上 x 的祖先（显然，x 的祖先一定可以到达 x）。记这个祖先为 z，则这条横叉边一定能和它到 z 的路径，z 到 x 的路径组成环。

为了找到横叉边与后向边组成的环，我们考虑在深度优先遍历的同时维护一个栈。

当遍历到 i 节点时，栈里一定有以下一些点：

1. 搜索树上 i 的所有祖先集合 j。若此时存在后向边 (i, j)，则 (i, j) 一定与 j 到 i 的路径形成环。
2. 已经访问过的点 k，且满足从 k 出发一定能找到到 j 的路径。此时，(i, k)，k 到 j 的路径，j 到 i 的路径一定会形成环。

于是我们引入回溯值的概念。回溯值 low[x] 表示以下节点的最小时间戳：

1. 该点在栈中。
2. 存在一条从流图的搜索树中以 x 为根的子树为起点出发的有向边，以该点为终点。（也就是以它为起点能继续往下遍历到的点）

如果当前的 low[x] 表示的最小时间戳代表的点集全是2类点，则易得 low[x] = dfn[x] 时强连通分量存在，且 x 是此强连通分量的根（整个强连通分量中时间戳最小的节点）。

如果表示的点集存在1类点。则当前点一定属于强连通分量，且该强连通分量的根为整个强连通分量中时间戳最小的节点。

当我们判断了存在以当前点为根的强连通分量后，从栈中不断取出点，直到取出的点与当前点相等，我们就得到了整个强连通分量的信息。

整理更新回溯值的方法：

1. 如果当前点第一次被访问，入栈，且 low[x] = dfn[x]。
2. 遍历从 x 为起点的每一条边 (x, y)。若 y 被访问过，且 y 在栈中，那么 low[x] = min(low[x], dfn[y])。若 y 没被访问过，递归访问 y，在回溯之后更新 low[x] = min(low[x], low[y])。（典型dp思想）

具体实现

int dfn[MAXN], low[MAXN];
// 时间戳及回溯值。
vector <int> scc[MAXN];
// 储存最后求出的各个强连通分量的信息。
int key[MAXN];
// key[i]表示i在编号为key[i]的强连通分量中。

stack<int> st; // 栈。
bool vis[MAXN];
// 记录是否在栈中。
int num = 0, cnt = 0; 
// num 时间戳标记。cnt 强连通分量标记。

void tarjan(int x) {
    num++; 
    dfn[x] = num;
    low[x] = num;
    st.push(x); 
    vis[x] = true;      
    // 第一次遍历到，记录时间戳，入栈，记录当前回溯值      
    for(int i = 0; i < map_first[x].size(); i++) { // 枚举每条边。
        int j = map_first[x][i];
        if(!dfn[j]) { // 如果当前边的终点没被遍历过。
            tarjan(j); // 递归遍历。
            low[x] = min(low[x], low[j]);
            // 维护回溯值。
        }
        else if(vis[j]) // 如果遍历过且在栈中。
            low[x] = min(low[x], dfn[j]);
            // 维护回溯值。
    }
    if(dfn[x] == low[x]) { // 如果存在以当前点为根的强连通分量。         
        cnt++;
        int now = 0;
        while(x != now) { // 找出栈中所有在当前强连通分量中的点。
            now = st.top();
            st.pop();
            vis[now] = false; 
            key[now] = cnt; // 存所在编号。
            scc[cnt].push_back(now); // 存点。
        }
    }   
}

缩点

缩点。其实就是指的把环看成一个点来进行后面的图论算法。而把环看成的这个点的点权在题目中会具体说明。

比较常见的缩点后的点权是整个环路的所有点的点权和。

如下图：

1 -> 2 -> 4 -> 5 -> 2 -> 3

显然上图存在环路。在经过缩点后，我们可以将它变成这样：

1 -> 2(value[2] + value[4] + value[5]) -> 3

思路比较简单，我就直接分析代码了。。。

具体实现

for(int i = 1; i <= n; i++) 
    for(int j = 0; j < map_first[i].size(); j++) {
        // 枚举原图中的每一条边。
        int v = map_first[i][j];
        if(key[i] == key[v]) 
        // 如果这个边的两端属于同一个强连通分量，则直接放弃这条连边。
            continue;
        map_second[key[i]].push_back(key[v]);
        // 将两个点对应的强连通分量的编号相连，加入新图。
        // 显然，单个点也属于一个强连通分量。
    }

现在，我们再来看看这道题。。。

分析

显然这道题是有环的对吧。

如果我们不考虑环的情况，其实就是一个很板白菜的题目。

我们可以采用拓扑排序的思路，遍历整个图，然后对于每个路径维护一下到当前点的最大距离，并维护一个这个路径上的最大值。

然后考虑有环，很简单，事先 Tarjan 缩点嘛/xyx

并且这道题是要累加路径上的点的和。所以缩点后的点就是当前强连通分量包含的所有点的点权和。

AC代码

#include <cstdio> 
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
int n, m;
int value[MAXN];

vector<int> map_first[MAXN]; 
// 原图。 
int dfn[MAXN], low[MAXN];

struct data {
    int ma, sum;
    data() {
        ma = 0;
        sum = 0;
    }
    data(int Ma, int S) {
        ma = Ma;
        sum = S;
    }
} scc[MAXN]; 
// Tarjan 求出的强连通分量中，维护两个信息。
// 1.ma 表示整个强连通分量的最大值。 
// 2.sum 表示整个强连通分量的点权和，即缩点后的点权。 
int key[MAXN];

stack<int> st;
bool vis[MAXN];
int num = 0, cnt = 0;

void tarjan(int x) { // tarjan 算法。 
    num++;
    dfn[x] = num;
    low[x] = num;
    st.push(x);
    vis[x] = true;              
    for(int i = 0; i < map_first[x].size(); i++) {
        int j = map_first[x][i];
        if(!dfn[j]) {
            tarjan(j);
            low[x] = min(low[x], low[j]);
        }
        else if(vis[j]) 
            low[x] = min(low[x], dfn[j]);
    }
    if(dfn[x] == low[x]) {          
        cnt++;
        int now = 0;
        while(x != now) {
            now = st.top();
            st.pop();
            vis[now] = false;
            key[now] = cnt;     
            scc[cnt].ma = max(scc[cnt].ma, value[now]);
            scc[cnt].sum += value[now];
            // 维护一下强连通分量的两个信息。 
        }
    }   
}

vector<int> map_second[MAXN]; // 新图。 
int in[MAXN]; // 拓扑排序，统计点的入度。 
int dp[MAXN][2];
// dp[i][0]表示到i点的最长路径。 
// dp[i][1]表示路径上的最大点权。 

void T_Sort() { // 拓扑。 
    queue<int> q;
    for(int i = 1; i <= cnt; i++) {
        dp[i][0] = scc[i].sum;
        dp[i][1] = scc[i].ma;
    }
    for(int i = 1; i <= cnt; i++) 
        if(!in[i]) 
            q.push(i);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(int i = 0; i < map_second[x].size(); i++) {
            int v = map_second[x][i];
            in[v]--;
            if(!in[v]) 
                q.push(v);
            if(dp[v][0] < dp[x][0] + scc[v].sum) {
                dp[v][0] = dp[x][0] + scc[v].sum;
                dp[v][1] = max(dp[x][1], scc[v].ma);
                // 更新最长路径及最大点权。 
            }
            if(dp[v][0] == dp[x][0] + scc[v].sum) 
                dp[v][1] = max(dp[v][1], dp[x][1]);
            // 如果有两条最长路径则记录两条路径中的最大值。 
        }
    }
}

int main() {
    scanf ("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf ("%d", &value[i]);
        key[i] = i;
    }
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf ("%d %d", &u, &v);
        map_first[u].push_back(v);
    }

    for(int i = 1; i <= n; i++)
        if(!dfn[i]) // 如果当前点没被遍历，则跑一遍 Tarjan。 
            tarjan(i); 

    for(int i = 1; i <= n; i++) 
        for(int j = 0; j < map_first[i].size(); j++) {
            int v = map_first[i][j];
            if(key[i] == key[v])
                continue;
            map_second[key[i]].push_back(key[v]);
            in[key[v]]++;
        }
    // 缩点，存新图。 

    T_Sort();
    int ans = 1;
    for(int i = 2; i <= cnt; i++) // 统计答案。 
        if(dp[i][0] > dp[ans][0] || (dp[i][0] == dp[ans][0] && dp[i][1] > dp[ans][1])) 
            ans = i;
    printf("%d %d", dp[ans][0], dp[ans][1]);
    return 0;
}