图上DP

图上动规

51nod 1274 最长递增数据
因为路径的要求是严格递增的,所以一条边不会经过多次。
考虑\(dp[i]\)表示顶点\(i\)的最长边数。如果考虑从小到大枚举边数,在加入当前边之前的边肯定都比它小,且假设加入的顺序递增。那么加入这条边时,有\(dp[e[i].x] = max(dp[e[i].x],dp[e[i].y]+1)\),反过来还要更新一下边的另一个点\(y\)。这样是完成了一次的更新。另外考虑有很多边一样的情况,此时这些边不满足递增,需要一起操作,由于\(dp\)可能反复更新,需要加个\(tmp\)防止此种情况发生。