网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Jan09]地震损坏
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 14:15 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 14:15 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 14:15 |
输入文件 | damage.in | 输出文件 | damage.out |
地震损坏[Hal Burch, 2004] 农夫John的农场遭受了一场地震.有一些牛棚遭到了损坏,但幸运地,所有牛棚间的路经都还能使用. FJ的农场有P(1 <= P <= 30,000)个牛棚,编号1..P. C(1 <= C <= 100,000)条双向路经联 接这些牛棚,编号为1..C. 路经i连接牛棚a_i和b_i (1 <= a_i<= P;1 <= b_i <= P).路经 可能连接a_i到它自己,两个牛棚之间可能有多条路经.农庄在编号为1的牛棚. N (1 <= N <= P)头在不同牛棚的牛通过手机短信report_j(2 <= report_j <= P)告诉FJ它 们的牛棚(report_j)没有损坏,但是它们无法通过没有路经和损坏的牛棚回到到农场. 当FJ接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚. 注意:前50次提交将提供在一些测试数据上的运行结果. PROBLEM NAME: damage 输入格式: * 第1行: 三个空格分开的数: P, C, 和 N * 第2..C+1行: 每行两个空格分开的数: a_i 和 b_i * 第C+2..C+N+1行: 每行一个数: report_j 样例输入 (damage.in): 4 3 1 1 2 2 3 3 4 3 输出格式: * 第1行: 一个数,最少不能回到农庄的牛的数目(包括损坏的牛棚). 样例输出 (damage.out): 3 输出解释: 牛棚2遭到损坏,导致牛棚2, 3, 4里面的牛无法回到农庄.