【题解】最长递增路径 [51nod1274]

【题目描述】

一个可能有自环有重边的无向图，每条边都有边权。输入两个整数 \(n,m\) 表示一共 \(n\) 个点，\(m\) 条边并且给出 \(m\) 条边的信息：连接点 \(x,y\)，边权为 \(w\)。你可以从任何点出发，任何点结束，可以经过同一个点任意次，但是同一条边不能经过多次，并且你走过的路必须满足所有边的权值严格单调递增，求最长能经过多少条边。

以此图为例，最长的路径是：

\(3,1,2,3,2\) 或 \(3,1,2,3,4\) ，其长度为 \(4\) 。

【样例】

【数据范围】

\(100\%\) \(1 \leqslant n,m\leqslant 5*10^4,\) \(1 \leqslant w \leqslant 10^9,\) \(0 \leqslant x,y \leqslant n-1\)

【分析】

对于某一条边的信息，记录其连接的两个点，每次贪心找出边权最小的，用它所连接的两个点相互更新对方。

为防止重复选择，开一个滚动数组，用上一次保存的信息来提供决策点，由于数组赋值的操作会消耗大量时间，所以另外记录每次修改的部分，更新完后只赋值这一部分。

但是题目要求路径中边权严格递增，实际查找中可能会有权值相同的边，所以在处理完一条边后还要继续查找，如果发现其边权与当前剩下可选边中最小的相等，那么需要把这条可选边也提出来更新一下信息（还是使用上一次保存的信息来进行决策）。

询问是经过边的数量最大，因此初始化全为 \(0\) 。

时间复杂度为：\(O(mlogm)\) 。

【Code】

#include<algorithm>

#include<cstdio>

#include<queue>

#define Re register int

using namespace std;

const int N=5e4+3;

int x,y,w,n,m,po,ans,f[N],dp[N];

struct QAQ{int x,y,w;inline bool operator<(QAQ o)const{return w>o.w;}}a,tmp[N];

priority_queue<QAQ>Q;

inline void in(Re &x){

    int f=0;x=0;char c=getchar();

    while(c<'0'||c>'9')f|=c=='-',c=getchar();

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

    x=f?-x:x;

}

int main(){

    in(n),in(m);

    while(m--)in(a.x),in(a.y),in(a.w),Q.push(a);

    while(!Q.empty()){

    	po=0;

    	QAQ a=Q.top();Q.pop();

    	x=a.x,y=a.y,w=a.w;tmp[++po]=a;

    	dp[x]=max(dp[x],f[y]+1);

    	dp[y]=max(dp[y],f[x]+1);

    	ans=max(ans,max(dp[x],dp[y]));

    	while(!Q.empty()&&w==Q.top().w){

            a=Q.top();Q.pop();

            x=a.x,y=a.y;tmp[++po]=a;

            dp[x]=max(dp[x],f[y]+1);

            dp[y]=max(dp[y],f[x]+1);

            ans=max(ans,max(dp[x],dp[y]));

    	}

    	for(Re i=1;i<=po;++i)x=tmp[i].x,y=tmp[i].y,f[x]=dp[x],f[y]=dp[y];

    }

    printf("%d",ans);

}

巴特西

【题解】最长递增路径 [51nod1274]

【题解】最长递增路径 [51nod1274]

【题目描述】

【分析】

【Code】

最新文章

热门文章