P2812 校园网络【[USACO]Network of Schools加强版】

    • 985通过
    • 2K提交
  • 题目提供者 Kwork
  • 评测方式 云端评测
  • 标签 图论 强连通分量,缩点 枚举,暴力
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    浙江省的几所OI强校的神犇发明了一种人工智能,可以AC任何题目,所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空,他们来找你帮助他们。

    题目描述

    共有n所学校(n<=10000)已知他们实现设计好的网络共m条线路,为了保证高速,网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机母鸡,能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机母鸡都可以使别的学校使用上软件。

    输入输出格式

    输入格式:

    第一行一个整数n。

    接下来n行每行有若干个整数,用空格空格隔开。

    第i-1行的非零整数x,表示从i到x有一条线路。以0作为结束标志。

    输出格式:

    第一行一个整数表示问题1的答案。

    第二行回答问题2.

    输入输出样例

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

    说明

    POJ原题。数据扩大了100倍。

    边数 $\leq5000000$

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