1. pku 1700 Crossing River (pku 3404 Bridge over a rough river)

就是最朴素的过桥问题，问最少所需时间

2. pku 2573 Bridge

在1的基础上加上过桥所需要的步骤

3. zju 1579 Bridge 

这里要用long long 真恶

4. hit 2540 Only One Boat

这个题目是过桥问题的变种,题目的意思就是有N队夫妻,现在要过河，但是只有一条船，并且船每次只能载两个人。要求每一个妻子不能在丈夫不在的情况下与其他男人在一起，无论是船上还是岸上都不可以。问最少的次数使得所有人过河，并打印具体的步骤(spj)。

这个问题最少次数其实是固定的，不难推出如果有n队夫妻，那么全部过河的最少次数是5*n-3。（这个原因我请教了这个题目的作者，他的意思是最优的策略一定是两个人坐船去彼岸，一个人坐船回此岸。因此最少次数是一定的)。知道了最少次数如何去打印具体步骤了，其实我们从样例中3队夫妻的说明中可以得到一些启发，就是说经过若干步之后可以使得一对夫妻"Leave"。 例如3队夫妻的时候，标号为1，2为第一对夫妻（奇数为男，偶数为女，下同）,标号为3，4为第二对夫妻，标号为5，6为第三对夫妻。那么由2，4首先坐船来到彼岸，然后2回去，2和6再来到彼岸回去，然后6回去，让1，3过来，然后1和2离开，3回头，3和5再过去，3和4离开，5回头，5和6过河并离开。 现在转换到n个人的情形。如果n=1或者2，那么很容易就能找到方案了，因此下面的情况针对n>=3的情况，我们可以先让2n和2n-2过河，然后2n回来。(注：这个时候所形成的局面是此岸有n-1对夫妻和一个丈夫，彼岸有一个该丈夫的妻子）。下面2n和2n-4过河，然后2n-4回来，2n-1和2n-3过河，2n和2n-1 离开，2n-3返回。（注：这个时候的局面是此案有n-2对夫妻和一个丈夫，彼岸有一个该丈夫的妻子）。可以看出这是一个递归的过程。下面实现就简单了。

5. zju 2288 Across the River

题目大意: n个男生和m个女生过河.只有一只船,船每次最多装k人且满足如下条件:

任何时候岸边(包括此岸和彼岸)和船上要么没女生.否则女生不比男生少，问最少要渡几次才能使得所有人渡河完毕。

这个题目如果没有说要求彼岸也满足这个要求（即女生不比男生少，或者没有女生），我们可以利用贪心算法解决。

可以总是先把男生给送到彼岸，然后剩下来的部分都是尽量在满足条件的情况下把男生往船上放，然后每次把船从彼岸送回来的人最好是女生。这样可以使得结果次数最少。

但是现在要求的是此案和彼岸都必须满足条件，这样的话我们就只能bfs搜了。数据量不算大。