这题是课上的例题。
可是今天再做却仍然不会……
给定一张有向图，求最长的边权递增路径。
很快可以想到 dp。
一开始的 dp 思路是对于没一条边，用起点的各个边去更新终点。但是这样复杂度是边数的平方（菊花图），渔神想出了化边为点跑最短路的巧妙做法，遗憾的是，菊花图照样把建边复杂度卡到平方。
边太麻烦想用点来记录状态又得记录到这个点的最后一条边的权值，复杂度同样是平方的。
然后就好好好打量打量这个 dp 了。用起点的各个边去更新终点，这里面只有比该点权值小的被使用了，也就是说，对于一条边，图上的其它部分不管怎么搞，它的所有贡献都来自和比它权值小的边。
那么按照边权排序，按照这个顺序来更新就可以了。
需要注意边权可以重复，所以得先记录所有的答案，到一块相同的边权处理完的时候再更新到 dp 数组里去。
输入规模大，得关流同步，因为这个 T 了一次。
代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
const int M = 300005, N = M;
struct twt { int u, v, w; bool operator < (twt b) const { return w < b.w; }; };
std::vector<std::pair<int, int> > cha;
int n, m, f[N], ans;
twt e[M];
void sync() {
for (int i = 0; i < (int)cha.size(); i++) {
f[cha[i].first] = std::max(f[cha[i].first], cha[i].second);
ans = std::max(ans, f[cha[i].first]);
}
cha.clear();
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m;
for (int i = 1; i <= m; i++)
std::cin >> e[i].u >> e[i].v >> e[i].w;
std::sort(e+1, e+1+m);
for (int i = 1; i <= m; i++) {
if (e[i].w != e[i-1].w) sync();
cha.push_back(std::make_pair(e[i].v, f[e[i].u] + 1));
}
sync();
std::cout << ans;
}