带权有向图求LIS

CF459E Pashmak and Graph

给一个带权有向图，求其中严格递增的最长路径的长度(算边数)。

分析：第一眼想到的肯定是dp，令f[i]表示以结点i结尾的最长路径长度，但是发现有后效性，没办法滴出答案。可以先对边权从小到大进行排序，然后扫描边，这样可以不用考虑边权之间的约束关系。假设扫描到一条边e[i]，从u指向v，那么可以直接更新f[v] = max(f[u]+1, f[v])，为什么可以直接更新呢？因为f[u]是由e[i]前面那些边权小于e[i]的边构成的，不用考虑边权的约束。
但是这样最后求出来的答案不是严格递增的，我们还需要考虑那些边权相同的边带来的相互影响。我们可以对边权相同的边一起考虑，假设e[i]到e[j]的边权相同，现在一次扫描这些边，把需要更新的f[i]先存到g[i]里面，等这些边权相同的边全部考虑完之后，再把g[]里的值赋给f[]。这样就行了。

#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 3e5+5;
struct edge{
    int u, v, w;
    friend bool operator < (const struct edge &a, const struct edge &b){
        return a.w < b.w;
    }
}e[maxn];
int n, m;
int f[maxn], g[maxn];          // f[v] = max(f[v], f[u]+1)
int sta[maxn], top;
inline int read(){
    int x=0; char ch = getchar();
    while (ch<'0' || ch>'9')    ch = getchar();
    while (ch>='0' && ch<='9'){
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x;
}
int main(){
    int ans = 0;
    n = read(), m = read();
    for (int i=1; i<=m; i++)    e[i].u = read(), e[i].v = read(), e[i].w = read();
    sort (e+1, e+m+1);
    top = 0;
    for (int i=1; i<=m; ){
        int j = i;
        while (e[i].w == e[j+1].w)  j++;
        for (int k=i; k<=j; k++)    if (f[e[k].u]+1 > f[e[k].v]){
            g[e[k].v] = max (f[e[k].u] + 1, g[e[k].v]);
            sta[++top] = e[k].v;
        }
        while (top){
            f[sta[top]] = max(f[sta[top]], g[sta[top]]);
            g[sta[top]] = 0;
            top--;
        }
        i = j+1;
    }
    for (int i=1; i<=n; i++)    ans = max(ans, f[i]);
    printf ("%d", ans);
    return 0;
}