題目：http://poj.org/problem?id=1236
給N(100)個點組成的有向圖，問：
1.至少要選幾個點當起點，能走過整張圖
2.至少要加幾條邊，可以讓整個圖任兩點能相互連通
程式碼：http://codepad.org/oZbfANRI
首先有一個很顯而易見的事：強連通分量縮點
因為一個強連通子圖內可以互相連通
就這兩問來說、這子圖內的點都是等價的
所以考慮一個DAG，很容易知道問題一的答案是入度為0的點數
對第二問，假設有x個入度為0的點、x的出度為0的點
那麼連結的方案很顯然是用x條邊把這2x個點串成一條環
類似的道理，如果x個入度0點、y的出度0，答案就是max(x,y)
另外需要回歸問題的定義，萬一整張圖就是一個強連通分量、答案應該要是0
沒有留言:
張貼留言