P4843 清理雪道

    • 102通过
    • 191提交
  • 题目提供者 无尽
  • 评测方式 云端评测
  • 标签 网络流
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    滑雪场坐落在FJ省西北部的若干座山上。

    从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。

    你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。

    由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。

    输入输出格式

    输入格式:

    输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。

    接下来的n行,描述1~n号地点出发的斜坡,第i行的第一个数为mi (0 <= mi < n) ,后面共有mi个整数,由空格隔开,每个整数aij互不相同,代表从地点i下降到地点aij的斜坡。每个地点至少有一个斜坡与之相连。

    输出格式:

    输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

    输入输出样例

    输入样例#1: 复制
    8
    1 3
    1 7
    2 4 5
    1 8
    1 8
    0
    2 6 5
    0
    输出样例#1: 复制
    4
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。