首页 > 代码库 > 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