zcmimi's blog
查看原题

点击跳转

#include<bits/stdc++.h>
using namespace std;
#define Fur(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
    int x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x;
}
const int nmax=5e4+5;
const int inf=0x7f7f7f7f;
struct node{
    int u,v,d;
    node(int u,int v,int d):u(u),v(v),d(d){};
    node(){};
    bool operator<(const node&rhs)const{
      return d<rhs.d;}
};
node ns[nmax];
void maxs(int &a,int b){
    if(a<b) a=b;
}
int g[nmax],dp[nmax];
int main(){
    int n=read(),m=read(),u,v,d;
    Fur(i,1,m) ns[i].u=read(),ns[i].v=read(),ns[i].d=read();
    sort(ns+1,ns+m+1);
    int last=0;
    Fur(i,1,m){
        if(i==m||ns[i].d<ns[i+1].d){
            Fur(j,last+1,i) g[ns[j].u]=dp[ns[j].u],g[ns[j].v]=dp[ns[j].v];
            Fur(j,last+1,i){
                maxs(dp[ns[j].u],g[ns[j].v]+1);
                maxs(dp[ns[j].v],g[ns[j].u]+1);
            }
            last=i;
        }
    }
    int ans=0;
    Fur(i,0,n-1) maxs(ans,dp[i]);
    printf("%d\n",ans);
}
51nod 1274 最长递增路径
comment评论
Search
search