CF960F Pathwalks

hgzxwzf · 2022-07-02 17:50:56 · 题解

第一眼看去很容易想到 LIS 问题，从而想到 DP 去解决这道题。

这个题和 LIS 的区别就是状态转移时还要保证两个点在原图中有边，而且以一个点可以由多个边转移过来，所以我们状态转移方程里要加上一维表示最后的边权。

定义 dp[i,w] 为以 i 结尾，最后一次边权为 w 的最长路径。

对于一条有向边 (u,v,w)，有 dp[v][w]=\max(dp[v][w],dp[u][w\prime]+1)(w\prime<w)。

如果直接暴力转移的话，我们要暴力枚举 w\prime，那时间复杂度和空间复杂度就成了 O(nm)，肯定是不可行的。

我们并不需要要枚举 w\prime，因为边总共只有 m，条，连向一个点的边最多只有 m 条，况且我们只考虑编号比 (u,v) 这条边小的。

我们可以对每个点用 map 维护。

首先在 map[u] 的第一关键字里二分查找 w，设指针位置为 it，那么 it-1 的第二关键字就是最大的 dp[u][w]。

同时我们要维护 map[v] 的第一关键字和第二关键字的双单调性，因为如果存在 dp[v][w\prime]<dp[v][w] 且 w\prime>w 那么 dp[v][w\prime] 肯定不是最优值。

通过维护双单调性，我们也保证了第一步的正确性，同样这么用 map 还有UVA12161，都运用到了 map 第一关键字的自动排序。

代码：

#include<cstdio>
#include<map>
#include<cstring>
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
const int N=1e5+10;
map<int,int>dp[N];
int find(int u,int x)
{
    auto it=dp[u].lower_bound(x);
    return it==dp[u].begin()?0:(--it)->second;
}
int main()
{
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    rep(i,1,m)
    {
        int u,v,k;
        scanf("%d%d%d",&u,&v,&k);
        int res=find(u,k)+1; 
        if(res>find(v,k))
        {
            auto it=dp[v].lower_bound(k);
            dp[v][k]=res;
            while(it!=dp[v].end()&&it->second<=res) dp[v].erase(it++);
        }
        ans=max(ans,res);
    }
    printf("%d",ans);
    return 0;
}