本文主要是介绍Codeforces Round #261 (Div. 2) E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
E. Pashmak and Graph
题意：一个带权有向图，没有重边，没有自环。求图的最长路径长度，使得该路径每一条边权都严格递增。
思路：先排序，然后dp。dp[u]表示以u为起点的最长递增路径长度，len[u]表示以u为起点的最长递增路径的第一条边权。权值递减扫描所有边，状态转移：dp[u]=max(dp[u],dp[v]+1)(存在边uv且权w(u,v)<len(v))。但是这个题发现满足转移条件不能立即进行状态转移，因为有权相同的边，如果立即转移可能会影响这些边的转移。处理方法是用一个队列把能转移的边先存起来，直到扫描到权减小以后，一次性将他们全部转移。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define INF 1000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010using namespace std; struct edge{int u;int v;int w;
};edge E[600010];bool cmp(edge e1,edge e2){return e1.w<e2.w;
}int dp[300010];
int len[300010];queue<int> que;
queue<int> update;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);int n;//点 int m;//边 while(cin>>n>>m){memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)len[i]=INF;for(int i=1;i<=m;i++){cin>>E[i].u>>E[i].v>>E[i].w;}sort(E+1,E+m+1,cmp);int ans=0;for(int i=m;i>=1;i--){if(E[i].w!=E[i+1].w){//一次性转移 while(!que.empty()){int cur=que.front();que.pop();len[cur]=E[i+1].w;dp[cur]=max(dp[cur],update.front());update.pop();ans=max(ans,dp[cur]);}}if( dp[E[i].u]<dp[E[i].v]+1 && (E[i].w<len[E[i].v]) ){//存在队列中 update.push(dp[E[i].v]+1);que.push(E[i].u);}}while(!que.empty()){int cur=que.front();que.pop();dp[cur]=max(dp[cur],update.front());update.pop();ans=max(ans,dp[cur]);}cout<<ans<<endl;}return 0;
}这篇关于Codeforces Round #261 (Div. 2) E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
