缩点

tarjan强连通分量 dp 最长链权值

题目描述

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 $n,m$

第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。

第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\to v$ 的有向边。

输出格式

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

样例 #1

样例输入 #1

2 2
1 1
1 2
2 1

样例输出 #1

2

提示

对于 $100\%$ 的数据，$1\le n\le 10^4$，$1\le m\le 10^5$，$0\le a_i\le 10^3$。

思路

同最大半连通子图, 若该图是DAG, 则可以直接dp求出最长路径。 这里就直接tarjan缩点建新图, 缩点的时候把强连通分量的点权值都加上即可。

点的权值可以看做从任意一点连到该点的边的权值, 如 点a 的权值为 10, 那么所有 ?-> a的边的权值都是10。

代码

const int N = 1e4 + 10, M = 2e5 + 10;
int n, m;
int value[N];
 
int h[N], hs[N], e[M], ne[M], w[M], idx;
 
int dfn[N], low[N], ts;
int stk[N], top;
bool instk[N];
int id[N], scnt, sccsize[N];
int f[N]; // dp最大点权之和
 
void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
 
void tarjan(int u)
{
    dfn[u] = low[u] = ++ts;
    stk[++top] = u, instk[u] = true;
 
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (instk[j])
            low[u] = min(low[u], dfn[j]);
    }
 
    if (low[u] == dfn[u])
    {
        ++scnt;
        int y;
        do
        {
            y = stk[top--];
            instk[y] = false;
            id[y] = scnt;
            sccsize[scnt] += value[y];
        } while (y != u);
    }
}
 
int main()
{
    mem(h, -1);
    mem(hs, -1);
    FasterIO;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> value[i];
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(h, a, b, value[b]);
    }
 
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    //缩点建边
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
            {
                add(hs, a, b, sccsize[b]);
            }
        }
    // 1-scnt 新图 做dp求最长路径
    int res = 0;
    for (int i = scnt; i >= 1; i--)
    {
        if (!f[i])
            f[i] = sccsize[i];
        for (int j = hs[i]; ~j; j = ne[j])
        {
            int k = e[j];
            f[k] = max(f[k], f[i] + sccsize[k]);
        }
        res = max(f[i], res);
    }
    cout << res << endl;
    return 0;
}