首页 > 代码库 > Codeforces 459E Roland and Rose
Codeforces 459E Roland and Rose
本以为是个树形DP，按照树形DP的方法在那里dfs，结果WA到死，因为它存在有向环，不是树，凡是存在环的情况切记不要用树形的方法去做
题目的突破点在于将边排完序之后，用点表示以该点为边结尾的最大长度，因为是按边排序从小到大加边，所以后面加的边肯定比前面的小。
要注意相同边的情况，要搞个缓冲，因为相同边的时候如果直接操作，可能会造成不应该有的影响。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n,m;const int N = 100010*3;struct edge{ int u,v,w; bool operator < (const edge& rhs) const{ return w<rhs.w; }}E[N];int dp[N];int last[N];int main(){ while (scanf("%d%d",&n,&m)!=EOF) { for (int i=0;i<m;i++){ scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w); } sort(E,E+m); memset(dp,0,sizeof dp); memset(last,0,sizeof last); for (int i=0;i<m;){ int j=i; while (E[i].w==E[j].w && j<m) j++; for (int k=i;k<j;k++){ last[E[k].v]=max(last[E[k].v],dp[E[k].u]+1); } for (int k=i;k<j;k++){ dp[E[k].v]=max(dp[E[k].v],last[E[k].v]); } i=j; } int ans=0; for (int i=1;i<=n;i++){ ans=max(ans,dp[i]); } printf("%d\n",ans); } return 0;}
Codeforces 459E Roland and Rose
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。