CF459E Pashmak and Graph && nyoj1208 水题系列【贪心+dp】

落日映苍穹つ 2022-08-11 05:29 13阅读 0赞

题目：[CF459E Pashmak and Graph][]

题意：给出n个点，m条边的图，然后让你每次只能向权值更大边走，求最大的边数。可以走多次

分析：由于点比较多，我们可以先对权值从小到大排序，然后从小的开始，更新它的到的节点的值为前一个节点值+1，但是还会出现权值相等成环的情况，所以我们可以对相等的进行延迟更新。

代码：

#include<cstdio>
    #include<algorithm>
    #include <cstring>
    using namespace std;
    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()
    {int n,m;
        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=i+1;   ///t数组延迟更新相等的
                }
                ans=max(ans,dp[i]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[CF459E Pashmak and Graph]: http://codeforces.com/problemset/problem/459/E

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1208C

CF1208C > 这场杜老师大战tourist的比赛怎么这么多人类智慧题。。。题意： > 构造一个 $ n \\times n $ 的矩阵，使得该矩阵...

迈不过友情╰/ 2024年04月20日 10:31/ 0 赞/ 99 阅读

相关 CF1208A

CF1208A 题意： > 就是把斐波那契数列的+改成异或，求第n项的值。解法： > 又是一个人类智慧题，打表找规律。 > 可以发现答案在 $...

雨点打透心脏的1/2处/ 2024年04月20日 10:30/ 0 赞/ 92 阅读

相关 CF1208D

CF1208D 题意； > 给你一个数组，要求支持单点修改和单点查询解法： > 直接线段树搞一搞就没了。 CODE： includ...

系统管理员/ 2024年04月20日 10:24/ 0 赞/ 97 阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 86 阅读

相关【DP】CF598E

[Problem - E - Codeforces][] ![ea06301014c348d39e3a5f448de96951.png][] Code： incl

深碍√TFBOYSˉ_/ 2024年03月22日 22:01/ 0 赞/ 98 阅读

相关【DP】CF Edu 21 E

[Problem - E - Codeforces][] 题意： ![c96fb68444bf465d95ac7bb92caf33cf.png][]![b7481c00b1

骑猪看日落/ 2024年03月09日 00:41/ 0 赞/ 95 阅读

相关 Codeforces 1208F Bits And Pieces 位运算 + 贪心 + dp

题意：给你一个序列a, 问a\[i\] ^ (a\[j\] & a\[k\])的最大值，其中i < j < k。思路：我们考虑对于每个a\[i\]求出它的最优解。因为是异或

向右看齐/ 2023年08月17日 17:22/ 0 赞/ 145 阅读

相关 CF459E Pashmak and Graph && nyoj1208 水题系列【贪心+dp】

题目：[CF459E Pashmak and Graph][] 题意：给出n个点，m条边的图，然后让你每次只能向权值更大边走，求最大的边数。可以走多次

落日映苍穹つ/ 2022年08月11日 05:29/ 0 赞/ 14 阅读

相关 codeforces 459C - Pashmak and Buses 【构造题】

题目：[codeforces 459C - Pashmak and Buses][] 题意：给出n个人，然后k辆车，d天时间，然后每天让n个人选择坐一辆车去上学，要

妖狐艹你老母/ 2022年08月11日 03:29/ 0 赞/ 119 阅读

相关洛谷p1208 水题贪心思想入门

题目描述由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。 Marry乳业从一些奶农手中采购牛奶，并且每一位

今天药忘吃喽~/ 2021年12月24日 08:07/ 0 赞/ 378 阅读