Codeforces 459E 最长路

bsny在玩一个游戏，这个游戏是在一个带权的有向图中，找一条路径，有个限制条件，这条路径中的权值必须严格增长，也就是如果bsny选择了1到2权值为3的边，那么下一条边的权值必须大于3。
现在问你，bsny最多能找到几条边构成这样的路径。

输入
首先输入n, m，表示n个点，m条边.
然后输入m条边，每条边信息由u, v, w组成，表示u到v (1 <= u, v <= n, u != v)有向边权值为w (1 <= w<= 10^5 ) .
输入可能有重边。

输出
输出最多几条边构成这样的路径。

样例输入
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4
样例输出
6

提示
【样例说明】
1->2->5->4->3->2->6
【数据规模和约定】
对于40%的数据， 2<=n<=1000;1<=m<=min(n∗(n−1),1000)
对于100%的数据， 2<=n<=3∗105;1<=m<=min(n∗(n−1),3∗105);1<=wi<=105
输入可能有重边，如:
1 2 3
1 2 5
表示1到2既有长度为3的边，又有长度为5的边
甚至可能
1 2 3
1 2 3
表示1到2有两条长度为3的边

Solution

题目要求边权递增，那么我们就对边权排序，这样就能直接从前面转移了。
可以得到朴素的dp方程如下：
有一条x->y的边：
f[y]=max(f[y],f[x]+1)
但是仔细想想，这样还是有问题的。
如果到达x的最优解的那条边权和当前边权一样的话，这个转移是不合法的。
所以我们必须把边权一样的都抽出来，再统一处理。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int n,m,tot,ans;
int f[300005],b[300005],c[300005],d[300005];
struct ty
{
int x,y,z;
}a[300005];
bool cmp(ty a,ty b)
{
return a.z<b.z;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m+1;i++)
{
int x=a[i].x,y=a[i].y,z=a[i].z;
if(z!=a[i-1].z)
{
for(int j=1;j<=tot;j++) d[j]=max(f[b[j]],f[c[j]]+1);
for(int j=1;j<=tot;j++) f[b[j]]=max(f[b[j]],d[j]);
tot=1;
b[tot]=y;
c[tot]=x;
}
else
{
tot++;
b[tot]=y;
c[tot]=x;
}
}
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
cout<<ans;
return 0;
}

最后

以上就是包容流沙为你收集整理的Codeforces 459E 最长路的全部内容，希望文章能够帮你解决Codeforces 459E 最长路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。