Codeforces Round #261 (Div. 2) E. Pashmak and Graph【DP】

Pashmak's homework is a problem about graphs. Although he always tries to do his homework completely, he can't solve this problem. As you know, he's really weak at graph theory; so try to help him in solving the problem.

You are given a weighted directed graph with n vertices and m edges. You need to find a path (perhaps, non-simple) with maximum number of edges, such that the weights of the edges increase along the path. In other words, each edge of the path must have strictly greater weight than the previous edge in the path.

Help Pashmak, print the number of edges in the required path.

Input

The first line contains two integers n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ min(n·(n - 1), 3·105)). Then, m lines follows. The i-th line contains three space separated integers: ui, vi, wi (1 ≤ ui, vi ≤ n; 1 ≤ wi ≤ 105) which indicates that there's a directed edge with weight wi from vertex ui to vertex vi.

It's guaranteed that the graph doesn't contain self-loops and multiple edges.

Output

Print a single integer — the answer to the problem.

   Sample test(s) 
 

     input 
   
3 3
1 2 1
2 3 1
3 1 1

     output 
   
1

     input 
   
3 3
1 2 1
2 3 2
3 1 3

     output 
   
3

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

     output 
   
6

Note

In the first sample the maximum trail can be any of this trails: $Codeforces Round #261 (Div. 2) E. Pashmak and Graph【DP】$ .

In the second sample the maximum trail is $Codeforces Round #261 (Div. 2) E. Pashmak and Graph【DP】$ .

In the third sample the maximum trail is $Codeforces Round #261 (Div. 2) E. Pashmak and Graph【DP】$ .

题意：给个不重边，不成环的，边带权的有向图，求最大权值和所经历的节点数

DP：dp[节点] = 最大节点数。既然要最大权值，那将边按权值排序，每次加入一条边（当权值相同时，将相同的一起加入）求出Max(dp[节点])就行了

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define NMAX 300002
#define INF 0x7F7F7F7F
#define MEM(a) memset(a,0,sizeof(a));
#define FOR(i,n) for(int i=0;i<n;i++)
#define FIN freopen("E.txt","r",stdin);
#define FOUT freopen("out.txt","w",stdout);
struct in
{
    int u,v,w;
    bool operator< (const in &A)const
    {
        return w < A.w;
    }
}a[NMAX];
bool cmp(struct in A,struct in B)
{
    return A.w < B.w;
}
int c[NMAX],tc[NMAX];
int main()
{
    int n,m;
    int ans,j;
    //FIN;
    scanf("%d%d",&n,&m);
    MEM(a);
    MEM(c);
    MEM(tc);
    FOR(i,m)
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
 //   sort(a,a+m,cmp);
    sort(a,a+m);
    ans = 0;
    FOR(i,m)
    {
        for(j = i; a[i].w == a[j].w && j < m; j++);
        for(int k = i; k < j; k++)
             tc[a[k].v] = max(tc[a[k].v],c[a[k].u]+1);
        for(int k = i; k < j; k++)
             c[a[k].v] = tc[a[k].v];
        i = j - 1;
    }
    for(int i = 1; i <= n; i++)
        ans = max(c[i],ans);
    cout<<ans<<endl;
    return 0;
}

C++的sor默认按＜号排序，对int自然可以，对结构体的就不行了，所以要重载小于号或者写比较函数函数

数组处理有点像母函数...

参考大神博客

秒客网

Codeforces Round #261 (Div. 2) E. Pashmak and Graph【DP】

相关文章