首页 > 代码库 > cf 459E

cf 459E

2024-07-18 01:02:19   218人阅读

cf459E 这题说的是 给定一个n点m条边的带边权的有向图，从中找出一条路径（可以带环），该路径包含的边数最多，并且要求路径中的权值必须严格递增，然后对边进行排序完个后采用dp去解特殊判断一下边权值相等的时候就ok了

#include <iostream>#include <string.h>#include <cstdio>#include <algorithm>/* run this program using the console pauser or add your own getch, system("pause") or input loop */using namespace std;const int maxn = 100005*3;struct edg{    int a,b,w;    bool operator <(const edg A)const {       return w<A.w||( w == A.w &&a<A.a );    }    void read(int &a1,int &b1, int &w1 ){         a1 = a;         b1=  b;         w1=w;    }}E[maxn];__int64 dp[2][maxn];int ma[2][maxn];int main(int argc, char *argv[]) {    int n,m;    while(scanf("%d%d",&n,&m)==2){              for(int i =0 ; i< m; ++i)              scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);              sort(E,E+m);              memset(dp,0,sizeof(dp));              memset(ma,0,sizeof(ma));            __int64 ans=0;            for(int i =0; i< m; ++i){                int a,b,w;                 E[i].read(a,b,w);                if(w > ma[1][a] && dp[1][b] < dp[1][a]+1 ){                   if(ma[1][b] != w){                       ma[0][b] = ma[1][b];                       dp[0][b] = dp[1][b];                       }                   dp[1][b]=dp[1][a]+1;                   ma[1][b]=w;                } else if(w>ma[0][a]&&dp[1][b]<dp[0][a] +1){                     if(ma[1][b] != w){                       ma[0][b] = ma[1][b];                       dp[0][b] = dp[1][b];                         }                     dp[1][b]=dp[0][a]+1;                     ma[1][b]=w;                }                 ans = ans> dp[1][b]? ans : dp[1][b];            }                   printf("%I64d\n",ans);    }    return 0;}
View Code

de 


联系
我们