比较巧的一道题。
考虑这题本质其实是一个有向图上边的 LIS。于是就可以用类似 LIS 的贪心方式来做,只是转移的时候多了一个限制而已。
具体的,对每个 $x$ 维护一个 `map` (或者线段树),存入边权值为 $v$ 时的最长递增路径。考虑每次加进来一条边 $(u,v,w)$,答案就是从 $u$ 的 map 里找出最大的小于 $w$ 的值,根据单调性可知这一定是小于 $w$ 的那个最大值。然后暴力改就好了。不难知道这样做每条边至多被加一次、删一次,复杂度是 $O(m\log n)$ 。
```cpp
#include <map>
#include <cstdio>
#include <algorithm>
using std :: map ;
using std :: lower_bound ;
#define en end
#define be begin
#define lbd lower_bound
const int N = 300010 ;
typedef long long ll ;
int ans ;
int res ;
int n, m ;
map <int, ll> lis[N] ;
int search(int x, int v){
int ret = 0 ;
auto p = lis[x].lbd(v) ;
ret = (p == lis[x].be()) ? 0 : ((-- p) -> second) ; return ret ;
}
int main(){
scanf("%d%d", &n, &m) ; int x, y, z ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d%d", &x, &y, &z) ;
res = search(x, z) ; ++ res ;
if (res > search(y, z)){
auto p = lis[y].lbd(z) ; lis[y][z] = res ;
for (auto q = p ; q != lis[y].en() ; ){
if ((q -> second) > res) break ; q = lis[y].erase(q) ;
}
}
ans = std :: max(ans, res) ;
}
printf("%d\n", ans) ; return 0 ;
}
```