C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1274 最长递增路径

Problem

一个无向图,可能有自环,有重边,每条边有一个边权。你可以从任何点出发,任何点结束,可以经过同一个点任意次。但是不能经过同一条边2次,并且你走过的路必须满足所有边的权值严格单调递增,求最长能经过多少条边。

Solution

排序,然后dp[i]代表到达这个点时的最大路径长度,每次更新,由于长度严格递增,所以暂时把新的值放到一个地方,等长度增加时再更新。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int MAXN=50020;
int dp[MAXN];
int n,m;
struct E{
int u,v,w;
}e[MAXN];
struct P{
int x,val;
};
queue<P>q;
int cmp(E x,E y){
return x.w<y.w;
}
int main(){
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
e[i]=(E){x,y,z};
}
sort(e+1,e+1+m,cmp);
P tmp1,tmp2;
e[0].w=-1;
for(int i=1;i<=m;i++){
if(e[i].w!=e[i-1].w){
while(!q.empty()){
P p=q.front();q.pop();
dp[p.x]=max(dp[p.x],p.val);
}
}
int u=e[i].u,v=e[i].v,w=e[i].w;
tmp1=(P){u,max(dp[u],dp[v]+1)};
tmp2=(P){v,max(dp[v],dp[u]+1)};
q.push(tmp1);
q.push(tmp2);
}
while(!q.empty()){
P p=q.front();q.pop();
dp[p.x]=max(dp[p.x],p.val);
}
int mx=0;
for(int i=0;i<n;i++){
mx=max(mx,dp[i]);
}
printf("%d\n",mx);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/28054/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!