UOJ Logo 蜗牛编程训练题库

JZOJ

#1600. USACO 2019 US Open Contest, Bronze Problem 2. Milk Factory--奶牛工厂

Statistics
时间限制:1s    空间限制:256MB    输入文件:factory.in    输出文件:factory.out
当前24小时内您还剩30次提交本题的机会

题目描述:

牛奶生意正红红火火!Farmer John的牛奶加工厂内有$N$个加工站,编号为$1 \ldots N$($1 \leq N \leq 100$),以及$N-1$条通道,每条连接某两个加工站。(通道建设很昂贵,所以Farmer John选择使用了最小数量的通道,使得从每个加工站出发都可以到达所有其他加工站)。

为了创新和提升效率,Farmer John在每条通道上安装了传送带。不幸的是,当他意识到传送带是单向的已经太晚了,现在每条通道只能沿着一个方向通行了!所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。

然而,Farmer John认为事情可能还不算完全失败,只要至少还存在一个加工站$i$满足从其他每个加工站出发都可以到达加工站$i$。注意从其他任意一个加工站$j$前往加工站$i$可能会经过$i$和$j$之间的一些中间站点。请帮助Farmer John求出是否存在这样的加工站$i$。

输入格式(文件名:factory.in):

输入的第一行包含一个整数$N$,为加工站的数量。以下$N-1$行每行包含两个空格分隔的整数$a_i$和$b_i$,满足$1 \leq a_i, b_i \leq N$以及$a_i \neq b_i$。这表示有一条从加工站$a_i$向加工站$b_i$移动的传送带,仅允许沿从$a_i$到$b_i$的方向移动。

输出格式(文件名:factory.out):

如果存在加工站$i$满足可以从任意其他加工站出发都可以到达加工站$i$,输出最小的满足条件的$i$。否则,输出$-1$。

输出样例:

3
1 2
3 2

输出样例:

2

Solutions

标题 发表者 发表日期
None