1171人阅读
题意：给出n个点，m条边的图，然后让你每次只能向权值更大边走，求最大的边数。可以走多次
分析：由于点比较多，我们可以先对权值从小到大排序，然后从小的开始，更新它的到的节点的值为前一个节点值+1，但是还会出现权值相等成环的情况，所以我们可以对相等的进行延迟更新。
#include&cstdio&
#include&algorithm&
#include &cstring&
const int N = 305000;
int dp[N],g[N];
///dp保存到当前位置的最大值 g保存到当前点的最大值
struct edge
int u,v,w;
bool operator &(const edge& obj) const
return w&obj.w;
} e[300010];
int main()
while(~scanf(&%d%d&,&n,&m))
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
for(int i=0; i&m; i++)
scanf(&%d%d%d&,&e[i].u,&e[i].v,&e[i].w);
sort(e,e+m);
int t=0,ans=0;
for(int i=0; i&m; i++)
dp[i]=g[e[i].u]+1;
//当前位置全部更新
if(e[i].w!=e[i+1].w)
//当前点只更新不相等的
for(int j=t; j&=i; j++)
g[e[j].v]=max(g[e[j].v],dp[j]);
///t数组延迟更新相等的
ans=max(ans,dp[i]);
printf(&%d\n&,ans);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：541195次
积分：8441
积分：8441
排名：第1628名
原创：314篇
评论：125条
(1)(2)(1)(4)(2)(1)(1)(2)(5)(10)(7)(2)(2)(8)(19)(42)(24)(37)(21)(1)(6)(17)(21)(10)(6)(1)(5)(6)(19)(3)(3)(5)(8)(2)(14)(2)