【1】PKU1094
思考難度不大，就是不斷在有向圖中加邊，求加了幾條邊以后，圖中出現(xiàn)一條連接N個點的簡單路徑（就是一條長度為(N-1)的鏈），或者圖中出現(xiàn)環(huán)。判定連接N個點的簡單路徑的算法：拓撲排序，若每次隊列中有且只有一個入度為0的點，則這樣的路徑存在，所排出的順序就是結(jié)果。注意兩點：
（1）如果在前面的若干條邊加入后，已經(jīng)找到了解，那么就輸出解，結(jié)束（不管后面的邊了，即使后面的邊加入后形成環(huán)也無視），數(shù)據(jù)：
In:
4 4
A<B
B<C
C<D
D<A
0 0
Out:
Sorted sequence determined after 3 relations: ABCD.(在前3條邊加入后已經(jīng)找到了解，此時無視第4條邊，直接結(jié)束)
（2）在拓撲排序中發(fā)現(xiàn)隊列中入度為0的點超過1個（即路徑不存在）時，不要直接退出，應該將排序過程進行完畢，因為可能圖中已經(jīng)形成環(huán)，此時直接輸出有環(huán)的結(jié)果，數(shù)據(jù)：
In:
6 6
A<B
B<C
C<D
D<E
A<F
E<C
0 0
Out:
Inconsistency found after 6 relations.(在第6條邊加入后，雖然拓撲排序中在A出隊后隊列中出現(xiàn)了BF兩個點，但不能退出，因為此時圖中已經(jīng)出現(xiàn)了環(huán)C->D->E->C，需要輸出有環(huán)的結(jié)果)
代碼：
【2】PKU1112：
本題極其猥瑣，先求二分圖強連通分支再DP，DP時還因為會涉及負數(shù)下標而被迫改用中點型數(shù)組，最可怕的是范圍問題（可能會超范圍），無語了……真痛苦啊……（本沙茶一開始老是查不出來哪里疵了，搞了個手打的SJ……）
【3】PKU1135：
本題的意思極難理解。可以將其類比為線段燃燒：有N個端點，M條線段連接它們，當某個端點被點燃后，與其關聯(lián)的所有線段也將被同時點燃，當某條線段燒光后，其相關聯(lián)的另一個端點將被它點燃（當該端點未燒掉時）。線段燃燒所需的時間與線段長度成正比，點燃燒的時間很短，忽略不計。在此過程中還有可能發(fā)生下面的事情：某條線段燃燒過程中，其另一端點也被點燃，此時該線段會在兩頭同時開始燒……現(xiàn)在，一開始點燃編號為1的點，求所有點和線段燒完的時間，以及最后燒完的線段（或點）。

分析：首先很容易發(fā)現(xiàn)一個事實，就是一個點開始燒的時間就是圖中從1到這個點的最短路長度，這樣，求出1到所有點的最短路長度，即得到了最后燒完的點的編號（最短路最長的點）。然后考慮線段，可以發(fā)現(xiàn)，圖中的線段分為兩類：設該線段兩端點的最短路長度分別為d0和d1(d0<=d1)，該線段的長度（燒完的時間）為len，則若d0+len=d1，則該線段不會出現(xiàn)兩頭同時在燒的情況（因為該線段是全部燒完后再點燃另一端），否則若d0+len>d1，則該線段會出現(xiàn)兩頭同時在燒的情況，此時，該線段全部燒完的時間為d0+(d0+len-d1)/2。取最大值即可。
代碼：