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搜了。數據量不算大。