思路：把边看成点，然后每条边只能从下面的边转移过来，我们将边按照u为第一关键字，w为第二关键字排序，这样就能用线段树维护啦。
1 #include<bits/stdc++.h> 2 #define LL long long 3 #define fi first 4 #define se second 5 #define mk make_pair 6 #define pii pair<int,int> 7 using namespace std; 8 9 const int N = 1e6 + 7; 10 const int M = 100 + 7; 11 const int inf = 0x3f3f3f3f; 12 const LL INF = 0x3f3f3f3f3f3f3f3f; 13 const int mod = 1e9 + 7; 14 15 16 int n, m, hs[N]; 17 18 struct node { 19int u, v, w; 20node(int u = 0, int v = 0, int w = 0) { 21 this -> u = u; 22 this -> v = v; 23 this -> w = w; 24} 25bool operator < (const node &rhs) const { 26 if(u == rhs.u) { 27 return w < rhs.w; 28 } else { 29 return u < rhs.u; 30 } 31} 32 } edge[N], edge2[N]; 33 34 35 struct seg_tree { 36struct node { 37 int mx, l, r; 38}a[N << 2]; 39 40void build(int l, int r, int rt) { 41 a[rt].l = l, a[rt].r = r; 42 if(l == r) return; 43 int mid = (l + r) >> 1; 44 build(l, mid, rt << 1); 45 build(mid + 1, r, rt << 1 | 1); 46} 47 48void update(int pos, int rt, int v) { 49 int l = a[rt].l, r = a[rt].r; 50 if(l == r) { 51 a[rt].mx = max(a[rt].mx, v); 52 return; 53 } 54 55 int mid = (l + r) >> 1; 56 57 if(pos <= mid) 58 update(pos, rt << 1, v); 59 else 60 update(pos, rt << 1 | 1, v); 61 62 a[rt].mx = max(a[rt << 1].mx, a[rt << 1 | 1].mx); 63} 64 65int query(int L, int R, int rt) { 66 int l = a[rt].l, r = a[rt].r; 67 if(l >= L && r <= R) { 68 return a[rt].mx; 69 } 70 71 int mid = (l + r) >> 1; 72 int ans = 0; 73 74 if(L <= mid) 75 ans = max(ans, query(L, R, rt << 1)); 76 if(R > mid) 77 ans = max(ans, query(L, R, rt << 1 | 1)); 78 79 return ans; 80} 81 }seg; 82 83 int main() { 84 85scanf("%d%d", &n, &m); 86 87for(int i = 1; i <= m; i++) { 88 scanf("%d", &edge[i].u); 89 scanf("%d", &edge[i].v); 90 scanf("%d", &edge[i].w); 91 edge2[i].u = edge[i].u; 92 edge2[i].v = edge[i].v; 93 edge2[i].w = edge[i].w; 94} 95 96sort(edge2 + 1, edge2 + m + 1); 97int ans = 0; 98 99seg.build(1, m, 1);100for(int i = m; i >= 1; i--) {101 int l = lower_bound(edge2 + 1, edge2 + m + 1, node(edge[i].v, 0, edge[i].w + 1)) - edge2;102 int r = lower_bound(edge2 + 1, edge2 + m + 1, node(edge[i].v + 1, 0, -1)) - edge2 - 1;103 int ret = 1;104 if(l <= r) {105 ret = max(ret, 1 + seg.query(l, r, 1));106 }107 int pos = lower_bound(edge2 + 1, edge2 + m + 1, edge[i]) - edge2;108 seg.update(pos, 1, ret);109}110 111printf("%d\n", seg.a[1].mx);112return 0;113 }114 115 /*116 */
