Pathwalks CodeForces - 960F （主席树，dp）

本文链接：https://blog.csdn.net/sunmaoxiang/article/details/102526954

本文介绍了解决最长链问题的一种高效算法，利用主席树优化动态规划过程，避免了传统线段树带来的内存溢出问题。通过实例代码详细解析了算法的实现细节。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目大意

给定一个n个点、m条边的有向图，然后要求一个最长链满足其链的顺序是按给定边的顺序的，其次保证其权值是单调递增。

思路

对于图中每个点我们可以开辟一个权值线段树，然后代表着以这个点结尾的边的权值之前的最长链长度，这样我们加一个新边长度为c，u->v时，就可以查询结点u的线段树，[1, c - 1] 最大值，然后+1更新c的最大值。

然后开辣么多权值线段树肯定会爆内存，不如用个主席树搞定。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 100;
int ls[N<<5],rs[N<<5],val[N<<5],rt[N],cnt=0;
int update(int k, int _val, int l, int r, int root) {
    int dir = ++cnt;
    ls[dir] = ls[root],rs[dir]=rs[root],val[dir] = max(val[root],_val);
    if(l == r) return dir;
    int mid = (l+r) >> 1;
    if(k <= mid) ls[dir] = update(k, _val, l, mid, ls[dir]);
    else rs[dir] = update(k, _val, mid + 1, r, rs[dir]);
    return dir;
}
int query(int root, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return val[root];
    int mid = (l+r) >> 1;
    int ret = 0;
    if(mid >= ql) ret=max(ret, query(ls[root], l, mid, ql, qr));
    if(mid < qr) ret=max(ret, query(rs[root], mid+1, r, ql, qr));
    return ret;
}
int main()
{
    //freopen("i.txt", "r", stdin);
    int n,m;
    scanf("%d%d", &n, &m);
    int ans = 0;
    for(int i = 0; i < m; i++) {
        int u,v,c;
        scanf("%d%d%d", &u, &v, &c);c+=2;
        int tmp = query(rt[u], 1, 100002, 0, c - 1);
        rt[v] = update(c, tmp+1, 1, 100002, rt[v]);
        ans=max(ans, tmp+1);
    }
    printf("%d\n", ans);
    return 0;
}
/*
3 3
3 1 3
1 2 1
2 3 2
*/