| 题目名称 | 1349. 计划 |
|---|---|
| 输入输出 | plan.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2013-04-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：5， 提交：21， 通过率：23.81% | ||||
 xiang |
100 | 0.005 s | 0.29 MiB | C++ |
 Tabing010102 |
100 | 0.006 s | 0.33 MiB | C++ |
 cstdio |
100 | 0.027 s | 2.81 MiB | C++ |
|
cstdio |
100 | 0.049 s | 4.25 MiB | C++ |
 digital-T |
100 | 0.953 s | 5.11 MiB | C++ |
|
xiang |
20 | 0.005 s | 0.29 MiB | C++ |
|
xiang |
20 | 0.005 s | 0.29 MiB | C++ |
|
xiang |
20 | 0.005 s | 0.29 MiB | C++ |
|
Tabing010102 |
20 | 0.007 s | 0.33 MiB | C++ |
|
digital-T |
20 | 0.009 s | 2.97 MiB | C++ |
| 本题关联比赛 | |||
| 20130415 | |||
| 关于 计划 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
第三个点的7卡的我自闭，7明明是另一颗树的根节点还有2个子节点为啥算可开发领域，真的好迷啊，最后也没懂什么情况，只能无脑说自己到自己的最难到，不管有没有子节点。这个1星题太社会了。
xiang
2018-12-03 21:41
4楼
| ||||
|
感谢两位前辈提供的指导，，然后，作为回归的第一个题，，代码跟shi一样，，，退化严重，，
 | ||||
|
当你惊奇的发现只过了2组时，我不会告诉你我发现了111到111有边要用dfs预处理一遍边
当你又惊奇的发现了改过还是只有2组时，我还不会告诉你其实111到111有边的时候其实它直接在处理完后判断是否与最不可能的冲突就可以了。。。 代码是越敲越恶心，敲2个下午你会发现你居然比别人慢10多倍，我都不吭。。。 | ||||
|
coding半小时，debug一下午+一晚上……忧桑逆流成河……
由于数据很弱所以事实上不用高精度orz（高精度事实上跪掉了虽然A过orz） | ||||
【问题描述】
SY战队的首领SYS最近几天很烦恼，SY战队想要继续开发新小陆，SYS必须马上制定出开发计划。新小陆可开发区域位于一片沼泽地中，数目不明，DD战队可以随便选择一个进行开发。SYS已经得到了前往沼泽地的地图，他可以清晰地看到自己所在的总部位于1号已开发区域，并且知道由1号已开发区域可以到达的每一片区域以及这些可以到达的区域可以到达的区域。这些区域包括已开发的和未开发（可开发）的，共有n个，每一个区域都有一个固定编号，从1~n；而且整个小陆刚好有n-1条路径。由一个区域到达另一个区域需要一天，并且到达这个新的区域后不会再返回。
虽然不知道新小陆可开发区域的具体位置，但是DDS知道它们有共同的特征：一旦进入将无路可走，即没有新的区域可以到达。有的区域比较贫瘠，称之为P区域，在P区域会因为各种问题不得不逗留一天，然后才能继续前进；假如可开发区域也是P区域，那么逗留几天显然不是问题,可开发区域和其他可开发区域等价。
知道这些并不能完全解决SYS的烦恼，由于SY战队的成员智商很低，到达一个区域后不知道权衡利弊，总是随便选择一个新的可以到达的区域前进，所以他们可能走了很久才到达一个可开发区域。
SY战队当然想尽量节省物资，所以战队只能提供足够m天使用的物资。DDS想知道他的队员们最不可能到达和最可能到达的可开发区域的编号，假如有多个地区情况类似，两个答案都输出编号最小的。
【输入格式】
第一行三个数，n,m,k。分别表示区域数目，物资可以承受的天数和P区域的数目；
第二行k个数（若k≠0），表示P区域的编号；
接下来n-1行，每行两个数表示相连的区域的编号。
【输出格式】
输出两行，第一行表示最不可能到达的可开发区域，第二行表示最可能到达的可开发区域。
【输入样例】
6 1 0 1 2 1 3 2 4 2 6 4 5
【输出样例】
5
3
【数据范围】
20%数据：2≤n<=20 ,2≤m≤50 ,0≤k≤5
100%数据：2≤n≤1000,2≤m≤1000; 0≤k≤100