首页 > 搜索 > DFS搜索 > HDU 3894-East and West-图-[解题报告]HOJ
2015
04-13

HDU 3894-East and West-图-[解题报告]HOJ

East and West

问题描述 :

TDB (Tie Dao Bu) is a magical department in TC (Tian Chao), as you all know… Now we have some emergency foods to transport from east TC to west TC. In order to avoid more tragedies, this time it’s your turn to act as the role of scheduling the trains…
There are N stations numbered from 1 to N in TC, connected by M undirected railways, guaranteeing that any of the two stations are reachable to each other.
The east of TC has E (numbered from 1 to E) stations, while the west has W (numbered from N-W+1 to N) stations. Initially, P trains filled with food are waiting at P different stations in the east. Your task is to schedule these trains, thus making them finally stopped at P different stations in the west.
Here, the time for a train to pass a single railway is exactly one day. And for safety reasons, each railway can let only one train pass per day. Moreover, a train can stop at any station for an arbitrarily number of days. And each station can hold at most P trains.
To simplify, we shall promise that M = N – 1 and N <= 10^6, and there always exists a railway whose removal separates the east and the west.
Your task is to make the trains’ arrival completed as soon as possible.

输入:

There are multiple test cases. For each test case, there will be 4 integers in the first line, namely N, M, E and W, as mentioned above. Each of the next M lines will contain two integers u and v, which indicates a railway between u and v. Then the following line has a single integer P. For the next P lines, each will contain a single integer describing the initial positions for the trains with food.

输出:

There are multiple test cases. For each test case, there will be 4 integers in the first line, namely N, M, E and W, as mentioned above. Each of the next M lines will contain two integers u and v, which indicates a railway between u and v. Then the following line has a single integer P. For the next P lines, each will contain a single integer describing the initial positions for the trains with food.

样例输入:

2 1 1 1
1 2
1
1

样例输出:

1

抓住题目给出的那个重要条件,就是E和W存在割边

接着就是找到那个最接近W的关键点,只要过了这个关键点,就不会存在什么时间相冲突

主要就是调整一下E这边的点到达这个关键点的时间顺序,按照关键点到达这个点的深搜深度,如果深度相同,就错开

接着先到的就去最远的W点,这样处理

图论,需要加强啊

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hqd_acm/article/details/6645468


,
  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥