题目链接：http://codeforces.com/contest/459/problem/E
题意：给一个带权有向图， 找出其中最长上升路的长度。
题解：先按权值对所有边排序， 然后依次 u ->v 权值w 则 f[u] = f[v] + 1; 这里需要注意的是 存在多条边权值相同， 这是应多条边一同计算。
1 /***Good Luck***/ 2 #define _CRT_SECURE_NO_WARNINGS 3 #include <iostream> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <stack> 10 #include <map> 11 #include <queue> 12 #include <vector> 13 #include <set> 14 #include <functional> 15 #include <cmath> 16 17 18 #define Zero(a) memset(a, 0, sizeof(a)) 19 #define Neg(a) memset(a, -1, sizeof(a)) 20 #define All(a) a.begin(), a.end() 21 #define PB push_back 22 #define inf 0x3f3f3f3f 23 #define inf2 0x7fffffffffffffff 24 #define ll long long 25 using namespace std; 26 //#pragma comment(linker, "/STACK:102400000,102400000") 27 const int maxn = 300005; 28 int dp[maxn], dp2[maxn]; 29 int rec[maxn]; 30 int n, e; 31 struct node { 32 int u, v; 33 int w; 34 }edge[maxn]; 35 36 37 bool cmp(node a, node b) { 38 return a.w < b.w; 39 } 40 int main() { 41 //freopen("data.out", "w", stdout); 42 //freopen("data.in", "r", stdin); 43 //cin.sync_with_stdio(false); 44 scanf("%d%d", &n, &e); 45 int u, v, w; 46 for (int i = 0; i < e; ++i) { 47 scanf("%d%d%d", &u, &v, &w); 48 edge[i].u = u; 49 edge[i].v = v; 50 edge[i].w = w; 51 } 52 sort(edge, edge + e, cmp); 53 int j; 54 for (int i = 0; i < e; ++i) { 55 for (j = i; j < e && edge[j].w == edge[i].w; ++j); 56 57 for (int k = i; k < j; ++k) { 58 dp2[edge[k].v] = max(dp2[edge[k].v], dp[edge[k].u] + 1); 59 } 60 for (int k = i; k < j; ++k) { 61 dp[edge[k].v] = dp2[edge[k].v]; 62 } 63 i = j - 1; 64 } 65 int ans = 0; 66 for (int i = 1; i <= n; ++i) { 67 ans = max(ans, dp[i]); 68 } 69 cout << ans << endl; 70 return 0; 71 }