BZPRO
#2771. YY的Train
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
YY在学会了Treap之后更加努力了，于是乎他的灵魂穿越了时空到达了3838年3月8日参加了第38届UOI，凭借着快速转换农历和阴历的能力，他拿到了金牌第38名。功成名就之后友爱的YY小朋友终于当上了火车调度员。现在小YY面临着一个难题，如何把湘江东岸的粮食运到湘江西岸去。湘江沿岸总共有N个火车站，这N个火车站由M条双向铁路连接，并且保证
任意两个站点可以互达
。湘江东岸有east个火车站，湘江西岸有west个火车站（
当然可能有站点设置在江中
），其中东岸有P个火车站中停留了一列装满粮食的火车。YY的任务是合理安排让这P列火车停在P个
不同的
西岸站点。每条铁路通过的时间都是一天，当然铁路部门为了保证安全要求每一天一条铁路只能通过一列火车。火车在到达目标之前可以在任意站点停留任意天，每个站点最多可以停留P列火车。上级部门要求YY拿出一套方案使得最晚到达的火车尽早到达。当然YY作为UOI金牌有更加重要的事情（要和Daren Nicholas打篮球啦，要和Luciano踢足球啦）所以这个任务就交给你啦。注意：
编号为1到east的是东边的火车站，编号为n-west+1到n的是西边的火车站
输入格式
第一行四个整数N,M,east,west
接下来M行每行两个整数u,v描述一条连通u,v的铁路
倒数第二行一个整数P
最后一行P个整数，表示P列火车停留的地方
输出格式
一个整数，表示最晚达到的火车达到的时间。
样例
样例输入
2 1 1 1
1 2
1
1
样例输出
1
数据范围与提示
n<=10^6,m=n-1,且保证存在一个站点将东岸和西岸的站点分开
此题为OJ2077
BZPRO