水题系列

时间限制：

1000 ms  |  内存限制：65535 KB

难度：

2

 

描述

    给你一个有向图，每条边都有一定的权值，现在让你从图中的任意一点出发，每次走的边的权值必须必上一次的权值大的情况下，问你最多能走几条边？

 

输入

首先一个n和m，分别表示点的数目和边的数目

接下来m行，每行三个值x,y,val，表示x到y有路，其权值为val。（1<n,m，val<10^5,0<x,y<=n）

输出

输出最多有的边的数目

样例输入

3 31 2 12 3 13 1 16 71 2 13 2 52 4 22 5 22 6 95 4 34 3 4

样例输出

16 解题思路：这个题目刚看起来好像是图论，但是出题人是考察的dp思想。定义两个数组dp[i],g[i]分别表示边编号为i时的最多有向边及点为i时的最多有向边数目。转移方程为： 　　　　　　如果边权不相同：dp[i]=g[E[i].st]+1,g[E[i].en]=max(g[E[i].en],dp[i])。 　　　　　　如果边权相同：{i,i+1,i+2,i+3...}边集合中都为边权相同的边编号。 　　　　　　　　　　　　　dp[i]=g[E[i].st]+1,dp[i+1]=g[E[i+1].st]+1，etc... 　　　　　　　　　　　　　g[E[i].en]=dp[i],g[E[i+1].en]=dp[i+1]，etc... 　　　　　　　　　　　　　对于边权相同的情况，第一组样例可以看出问题，这里这种操作学长说是延迟，具体说应该是对点延迟，对边提前。

#include
       
        using namespace std;const int maxe=1e5+10;struct edge{    int st,en;    int val;}E[maxe];int dp[maxe],g[maxe];int INF=1e9;bool cmp(edge a,edge b){    return a.val
        
         max_e){//            max_e=g[i];//        }//    }        for(int i=0;i