51nod 1274 最长递增路径（DP）

　　一开始自己想了一种跑的巨慢。。写了题解的做法又跑的巨快。。一脸懵逼

　　显然要求边权递增就不可能经过重复的边了，那么设f[i]为第i条边出发能走多远就好了，这是我一开始的写法，可能dfs冗余状态较多，跑的极慢

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,dis,pre;}e[maxn];

int n,m,x,y,z,tot,ans;

int last[maxn],dp[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

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

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;}

int dfs(int x,int fa)

{

    if(dp[x])return dp[x];dp[x]=;

    for(int i=last[e[x].too];i;i=e[i].pre)

    if(i!=fa&&e[i].dis>e[x].dis)dfs(i,x),dp[x]=max(dp[x],dp[i]+);

    return dp[x];

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);

    for(int i=;i<=tot;i++)if(!dp[i])dfs(i,);

    for(int i=;i<=tot;i++)ans=max(ans,dp[i]);

    printf("%d\n",ans);

    return ;

}

　　题解的做法是按照边权排序，然后就可以用点来转移了...

　　（然后就踩在yyl头上了

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int x,too,dis;}e[maxn];

int n,m,x,y,z,ans,last;

int g[maxn],f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

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

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.dis<b.dis;}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)read(x),read(y),read(z),e[i].x=x,e[i].too=y,e[i].dis=z;

    sort(e+,e++m,cmp);last=;

    for(int i=;i<=m;i++)

    if(i==m||e[i].dis<e[i+].dis)

    {

        for(int j=last;j<=i;j++)

        g[e[j].too]=f[e[j].too],g[e[j].x]=f[e[j].x];

        for(int j=last;j<=i;j++)

        f[e[j].too]=max(f[e[j].too],g[e[j].x]+),f[e[j].x]=max(f[e[j].x],g[e[j].too]+);

        last=i+;

    }

    for(int i=;i<n;i++)ans=max(ans,f[i]);

    printf("%d\n",ans);

    return ;

}