本文共 1128 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

给出n个点,m条边的有向图，每个边有边权，求一条最长的边权上升的路径的长度。

题目分析：

• 定义dp[i]表示第i条边结尾的情况下的最长路径。
• 定义g[i]表示点i结尾的情况的最长路径。
• 对所有的边进行排序，那么前面的边只可能小于等于后面的边。
• 所以dp[i] = g[e[i].u]+1
• 然后只需要特殊考虑一下边相等的情况，更新g[i]即可，具体见代码。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 300007using namespace std;int n,m;int dp[MAX],g[MAX];struct Edge{    int u,v,w;    bool operator < ( const Edge& a ) const    {        return w < a.w;    }}e[MAX];int main ( ){    while ( ~scanf ( "%d%d" , &n , &m ) )    {        for ( int i = 0 ; i < m ; i++ )            scanf ( "%d%d%d" , &e[i].u , &e[i].v , &e[i].w );        sort ( e , e+m );        int t = 0;        e[m].w = -1;        int ans = 0;        for ( int i = 0 ; i < m ; i++ )        {            int v = e[i].v;            int u = e[i].u;            int w = e[i].w;            dp[i] = g[e[i].u]+1;            if ( e[i].w != e[i+1].w )            {                for ( int j = t ; j <= i ; j++ )                    g[e[j].v] = max ( g[e[j].v] , dp[j] );                t = i+1;            }            ans = max ( ans , dp[i] );        }        printf ( "%d\n" , ans );    }}
      
     
    
   

转载地址：http://lqvjn.baihongyu.com/