USACO Training 5.3.3 Network of Schools 题解与分析

Network of Schools 校园网

IOI '96 Day 1 Problem 3

描述

部分高校接入了一个计算机网络系统。这些 school 已经签署了协议：每所学校都会向其他的一些 school 分发软件（称为接受者）。请注意：即使 B 学校将软件加入到 A 学校的分发列表中（即 A 校被视为 B 校的一个接收者），但反过来的情况则不一定成立：A 校可能不会将该软件添加到自己的接收方列表里。

你需要编写一个程序来计算，在协议框架下完成两个关键目标：首先确定最小数量的新软件副本接收者（即最少需要接收的新软件副本数量），使得从任意一所学校发送新软件后都能覆盖整个网络中的所有学校；其次确定最小的扩展次数（即通过添加最少数量的新成员到现有接收列表中），以确保无论从哪所学校的系统出发发送新软件都会覆盖整个网络的所有节点（即最少需要引入多少个新的成员）。这里的"扩展"特指在某一所学校的名字或标识码列表中添加一个新的联系对象或访问点

格式

PROGRAM NAME: schlnet

输入文件的第一行是一个整数N：表示网络中的学校数目（其中2 \leq N \leq 100）。每个学校被分配前N个正整数中的一个唯一标识符。\n\n接下来有N行数据，每行为接收学校的列表（即分发列表）。具体来说，在第i+1行中会列出第$i