【校内训练2019-11-14】战争

【题目概括】

给定一张无向带权图，求一条最长的边权严格递增路径的长度。

【思路要点】

【代码】

//program by author at the test
#include<bits/stdc++.h>

#define FI first
#define SE second
#define mp make_pair

using namespace std;

template<class T>void chkmin(T&x,T y){x=min(x,y);}
template<class T>void chkmax(T&x,T y){x=max(x,y);}

template<class T>
void re(T&x){
  x=0;char ch=0;int f=1;
  for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  for(;isdigit(ch);ch=getchar())x=x*10+ch-48;
  x*=f;
}

typedef pair<int,int> pii;

const int N=100005,M=200005;

struct _edge{
  int to,nt,w;
}E[M];

struct Edge{
  int u,v,w;
  bool operator<(const Edge&rhs)const{
    return w>rhs.w;
  }
}edge[M];

int n,m,edgeCnt,cnt;
int H[N],st[N],dp[M];
pii buf[M];

void addEdge(int u,int v,int w){
  E[++edgeCnt]=(_edge){v,H[u],w};
  H[u]=edgeCnt;
}

int main(){
  re(n),re(m);
  for(int i=1;i<=m;i++){
    re(edge[i].u),re(edge[i].v),re(edge[i].w);
    edge[i].u++,edge[i].v++;
    edge[m+i]=edge[i];
    swap(edge[m+i].u,edge[m+i].v);
    addEdge(edge[i].u,edge[i].v,edge[i].w);
    addEdge(edge[i].v,edge[i].u,edge[i].w);
  }
  sort(edge+1,edge+1+m*2);
  for(int i=1;i<=m*2;i++){
    if(edge[i].w!=edge[i-1].w){
      for(int j=1;j<=cnt;j++)
        chkmax(st[buf[j].FI],buf[j].SE);
      cnt=0;
    }
    int v=edge[i].v;
    dp[i]=st[v]+1;
    buf[++cnt]=mp(edge[i].u,dp[i]);
  }
  int ans=0;
  for(int i=1;i<=m*2;i++)
    chkmax(ans,dp[i]);
  cout<<ans<<'\n';
  return 0;
}