P1137 旅行计划

    • 1.3K通过
    • 3.3K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 图论 拓扑排序 排序 递推
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小明要去一个国家旅游。这个国家有# $N$ 个城市,编号为 $1$ 至 $N$ ,并且有 $M$ 条道路连接着,小明准备从其中一个城市出发,并只往东走到城市i停止。

    所以他就需要选择最先到达的城市,并制定一条路线以城市i为终点,使得线路上除了第一个城市,每个城市都在路线前一个城市东面,并且满足这个前提下还希望游览的城市尽量多。

    现在,你只知道每一条道路所连接的两个城市的相对位置关系,但并不知道所有城市具体的位置。现在对于所有的i,都需要你为小明制定一条路线,并求出以城市 $i$ 为终点最多能够游览多少个城市。

    输入输出格式

    输入格式:

    第 $1$ 行为两个正整数 $N, M$ 。

    接下来 $M$ 行,每行两个正整数 $x, y$ ,表示了有一条连接城市 $x$ 与城市 $y$ 的道路,保证了城市 $x$ 在城市 $y$ 西面。

    输出格式:

    $N$ 行,第 $i$ 行包含一个正整数,表示以第 $i$ 个城市为终点最多能游览多少个城市。

    输入输出样例

    输入样例#1: 复制
    5 6
    1 2
    1 3
    2 3
    2 4
    3 4
    2 5
    
    输出样例#1: 复制
    1
    2
    3
    4
    3
    

    说明

    均选择从城市1出发可以得到以上答案。

    对于 $20\%$ 的数据, $N ≤ 100$ ;

    对于 $60\%$ 的数据, $N ≤ 1000$ ;

    对于 $100\%$ 的数据, $N ≤ 100000,M ≤ 200000$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。