缩点(洛谷p3387) [tarjan缩点模板题]

Description

• 给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
• 允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

Input

• 第一行两个正整数 n,m。
• 第二行 n个整数，依次代表点权
• 第三至 m+2 行，每行两个整数 u,v，表示一条 u→vu→v 的有向边。

Output

• 共一行，最大的点权之和。

Sample Input

2 2
1 1
1 2
2 1

Sample Output

2

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct edge{
    int from, to, nx;
}e[maxn << 1], g[maxn << 1];//分别存储原图和缩点后的DAG
int lene, leng, heade[maxn], headg[maxn];
int Time, dfn[maxn], low[maxn], vis[maxn], s[maxn], top;
int dp[maxn], n, m, sum[maxn], a[maxn], tot, belong[maxn];//belong记录所属环编号
void Insert(int x, int y, int flag){//插边,flag表示往哪张图插边
    if(flag == 1){
        e[++lene].from = x;
        e[lene].to = y;
        e[lene].nx = heade[x];
        heade[x] = lene;
    }else{
        g[++leng].from = x;
        g[leng].to = y;
        g[leng].nx = headg[x];
        headg[x] = leng;
    }
}
void tarjan(int u){
    dfn[u] = low[u] = ++Time; //默认值
    vis[u] = 1;
    s[++top] = u;
    for(int i=heade[u]; i; i=e[i].nx){
        int v = e[i].to;
        if(!dfn[v]){//如果未访问过
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(vis[v]) low[u] = min(low[u], dfn[v]);//如果是返祖边
    }
    if(dfn[u] == low[u]){//一个环的起点
        ++tot;//点数加一
        while(s[top+1] != u){//从栈顶到u的点缩成一个新点tot
            int v = s[top];
            belong[v] = tot;
            vis[v] = 0;
            sum[tot] += a[s[top--]];
        }
    }
}
void dfs(int u){//dfs计算最大权值
    if(dp[u]) return;
    dp[u] = sum[u];
    for(int i=headg[u]; i; i=g[i].nx){
        int v = g[i].to;
        dfs(v);
        dp[u] = max(dp[u], dp[v] + sum[u]);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=m; i++){
        int x, y; scanf("%d%d", &x, &y);
        Insert(x , y, 1);
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);//缩点
    for(int i=1; i<=n; i++){//建新图
        int u = e[i].from, v = e[i].to;
        if(belong[u] != belong[v]) Insert(belong[u], belong[v], 2);
    }
    int ans = 0;
    for(int i=1; i<=tot; i++){//dfs获得最大权值
        if(!dp[i]){
            dfs(i);
            ans = max(ans, dp[i]);
        }
    }
    printf("%d
", ans);
    return 0;
}