Problem
給一張圖有 N 個節點、M 條邊,其中要放置 S 台新主機於其中 S 個節點,而沒放置的節點繼續使用舊主機,為了服務舊主機的網咖,每個舊節點旁邊最多只能有一個新主機網咖。
請問有多少種放置方法。
Sample Input
|
|
Sample Output
|
|
Solution
對於每一個節點的連接方式用一個 32-bit 壓縮,接著窮舉所有可能放置方法 state,對於沒有放置的節點,直接壓縮結果與 state 做 AND 運算,算 bits 數是否都小於 2。
|
|
給一張圖有 N 個節點、M 條邊,其中要放置 S 台新主機於其中 S 個節點,而沒放置的節點繼續使用舊主機,為了服務舊主機的網咖,每個舊節點旁邊最多只能有一個新主機網咖。
請問有多少種放置方法。
|
|
|
|
對於每一個節點的連接方式用一個 32-bit 壓縮,接著窮舉所有可能放置方法 state,對於沒有放置的節點,直接壓縮結果與 state 做 AND 運算,算 bits 數是否都小於 2。
|
|