问题1010--最长路

1010: 最长路

时间限制: 1 Sec  内存限制: 128 MB
提交: 118  解决: 46
[提交] [状态] [讨论版] [命题人:]

题目描述

bsny在玩一个游戏,这个游戏是在一个带权的有向图中,找一条路径,有个限制条件,这条路径中的权值必须严格增长,也就是如果bsny选择了12权值为3的边,那么下一条边的权值必须大于3

现在问你,bsny最多能找到几条边构成这样的路径。

输入

首先输入n, m,表示n个点,m条边.

然后输入m条边,每条边信息由u, v, w组成,表示uv (1 <= u, v <= n, u != v)有向边权值为w (1 <= w<= 10^5 ) .

输入可能有重边。

输出

输出最多几条边构成这样的路径。

样例输入 Copy

6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4

样例输出 Copy

6

提示

【样例说明】

1->2->5->4->3->2->6

【数据规模和约定】

对于40%的数据,2<=n<=1000;  1<=m<=min( n*(n-1), 1000)

对于100%的数据,2<= n <= 3*10^5;  1<= m <= min(n*(n-1), 3*10^5);  1 <= wi <= 10^5

输入可能有重边,如:

1 2 3

1 2 5

表示12既有长度为3的边,又有长度为5的边

甚至可能

1 2 3

1 2 3

表示12有两条长度为3的边

来源/分类

cf459E