TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6648
  • 题目
  • P6648清理雪道
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    滑雪场坐落在FJ省西北部的若干座山上。
    从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。
    你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。
    由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。

    输入格式

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

    输出格式

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

    样例输入

    8
    1 3
    1 7
    2 4 5
    1 8
    1 8
    0
    2 6 5
    0

    样例输出

    4


    来源  bzoj2502