《CF960F Pathwalks》

题目描述

给定 n 个点 m 条边的有向图，可能不连通，可能有重边，也可能会有自环。求最长的路径(可以经过重复节点)，使得这条路径的编号和权值都严格单调递增，其中编号指输入的顺序。路径的长度是指经过边的数量。

输入格式

第一行两个整数 n,m。

第二行到第 m+1 行，每行三个整数 a,b,k，表示顶点 a 与顶点 b 有一条边相连，边权为 k。

输出格式

一行一个整数，表示最长的路径的长度。

1≤n,m≤105，0≤wi​≤105。

retranslated by @皎月半洒花。

显示翻译

题意翻译

输入输出样例

输入 #1复制

3 3 3 1 3 1 2 1 2 3 2

输出 #1复制

2

输入 #2复制

5 5 1 3 2 3 2 3 3 4 5 5 4 0 4 5 8

输出 #2复制

3

代码实现：

#include<bits/stdc++.h> #define x first #define y second #define il inline #define low(x) x&-x #define ls(x) x<<1 #define rs(x) x<<1|1 #define pb(x) push_back(x) #define gcd(x,y) __gcd(x,y) #define lcm(x,y) x*y/gcd(x,y) using namespace std; typedef pair<int,int> pii; typedef pair<int,pii> PII; const int N=30*1e5+10, INF=1e9+7; int n, m; int cnt=0; int rt[N], tr[N]; int lc[N], rc[N]; il int rd(){ int x=0, f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-48; c=getchar(); } return x*f; } il void pushup(int u){ tr[u] = max(tr[lc[u]], tr[rc[u]]); } il int upd(int u, int l, int r, int x, int w){ if(!u) u=++cnt; if(l==r){ tr[u] = max(tr[u], w); return u; } int mid=l+r>>1; if(x<=mid) lc[u] = upd(lc[u], l, mid, x, w); else rc[u] = upd(rc[u], mid+1, r, x, w); pushup(u); return u; } il int qry(int u, int l, int r, int ql, int qr){ if(!u) return 0; if(ql<=l&&r<=qr) return tr[u]; int mid=l+r>>1, res=0; if(ql<=mid) res = qry(lc[u], l, mid, ql, qr); if(qr>mid) res = max(res, qry(rc[u], mid+1, r, ql, qr)); return res; } signed main(){ int ans=0; n=rd(), m=rd(); while(m--){ int u=rd(), v=rd(), w=rd(); int x = qry(rt[u], 0, 1e5, 0, w-1)+1; rt[v] = upd(rt[v], 0, 1e5, w, x); } for(int i=1;i<=n;i++) ans = max(ans, tr[rt[i]]); printf("%d\n", ans); return 0; }