題目連接：http://codeforces.com/contest/459/problem/E
題目大意：給定一張有向圖，無自環無重邊，每條邊有一個邊權，求最長嚴格上升路徑長度。(1≤n，m≤3 *10^5)
初見此題覺得以邊為點，以點為邊，重建一張圖，小邊權向（通過點）相鄰的大邊權連邊，然后得到一張DAG，跑最長DAG路即可。然而仔細一想，這樣新圖邊數上限可以達到m^2。被否決。
后來想到邊權有序化思想（并不知道怎么想到的…可能受kruskal思想影響），按邊從大到小排序，然后一條邊一條邊加入，對于u->v這樣一條邊，dp[u] = max(dp[u], dp[v] + 1)，之所以從大到小排是為了保證狀態轉移的正確性（與上升路徑有關），實際上也就確定了dp的順序。特殊些的是，對于邊權相同的邊，不能逐條加入，因為題目要求嚴格單增，邊權相等的時候先加的可能影響后加的轉移正確性。因此把邊權相同的邊同時更新同時加入（用另外一個數組先記下值，再更新dp）。最后答案就是所有點的dp值中取最大。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;const int MaxN = 3 * 1e5;
struct EDGE
{int u, v, w;
}edge[MaxN + 5];
int n, m, res = 0, ans[MaxN + 5], t[MaxN + 5];bool cmp(EDGE x, EDGE y)
{return x.w > y.w;
}void Init()
{scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++)scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);sort(edge + 1, edge + m + 1, cmp);
}void Solve()
{memset(ans, 0, sizeof(ans));int head = 1, tail;while (head <= m){tail = head;while (tail <= m - 1 && edge[tail + 1].w == edge[tail].w) tail++;for (int i = head; i <= tail; i++) t[edge[i].u] = ans[edge[i].u];for (int i = head; i <= tail; i++)t[edge[i].u] = max(t[edge[i].u], ans[edge[i].v] + 1); for (int i = head; i <= tail; i++) ans[edge[i].u] = t[edge[i].u];head = tail + 1; }for (int i = 1; i <= n; i++) res = max(res, ans[i]);printf("%d\n", res);
}int main()
{Init();Solve();
}
)
)
