Codeforces 459E Roland and Rose

本以为是个树形DP，按照树形DP的方法在那里dfs，结果WA到死，因为它存在有向环，不是树，凡是存在环的情况切记不要用树形的方法去做

题目的突破点在于将边排完序之后，用点表示以该点为边结尾的最大长度，因为是按边排序从小到大加边，所以后面加的边肯定比前面的小。

要注意相同边的情况，要搞个缓冲，因为相同边的时候如果直接操作，可能会造成不应该有的影响。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
const int N = 100010*3;
struct edge
{
    int u,v,w;
    bool operator < (const edge& rhs) const{
        return w<rhs.w;
    }
}E[N];
int dp[N];
int last[N];
int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        for (int i=0;i<m;i++){
            scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
        }
        sort(E,E+m);
        memset(dp,0,sizeof dp);
        memset(last,0,sizeof last);
        for (int i=0;i<m;){
            int j=i;
            while (E[i].w==E[j].w && j<m) j++;
            for (int k=i;k<j;k++){
                last[E[k].v]=max(last[E[k].v],dp[E[k].u]+1);
            }
            for (int k=i;k<j;k++){
                dp[E[k].v]=max(dp[E[k].v],last[E[k].v]);
            }
            i=j;
        }
        int ans=0;
        for (int i=1;i<=n;i++){
            ans=max(ans,dp[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}