題意：https://loj.ac/problem/2540

給定一個圖(n<=20)，定義一個求最大獨立集的隨機化算法

產生一個排列，依次加入，能加入就加入

求得到最大獨立集的概率

?

loj2540 「PKUWC 2018」隨機算法

本質就是計數題

每個點有三種狀態：考慮過且在獨立集中，考慮過未在獨立集中，未考慮

本來在集合里的點不能知道有哪些，而且不能加入的點的排列也不好確定。

一個好的方法是：把考慮過的點放在一起

然后在加入一個點的時候，把其他不能加入的點都考慮上，并處理方案數。

?

設f[i][S]表示，獨立集大小為i，不能再選擇的點集合是S的方案數

每次選擇一個能加入的點j，然后更新能選擇的集合和集合大小，順便處理排除掉的點的方案數

就是一個排列，其實就是把后面尚未考慮的位置加入一下，

注意這里不用考慮j的位置，j位置欽定為從前往后第一個能選擇的位置

i從n往下找到第一個方案數不是0的f[k][全集]

最后乘上n！的逆元即可

O(n^2*2^n)傳說可過

?

對于不可以選擇的集合S,對應的最大獨立集確定

mxS記錄S集合最大獨立集

所以類似最短路條數，mxS更新的時候，把方案數設成0

這樣也能求出最大獨立集方案數。

O(n*2^n)

?

思路有點類似某次模擬賽T3，我在加入一個數的時候，就把能產生的貢獻和影響都計算上

因為只有在枚舉這個轉移的時候才知道加入的哪個點，這樣不用考慮加入進去的點都是誰了。

也方便處理不能選擇的那些點的排列。

?

（有了第二種做法，一般的20個點的最大獨立集也可以做了，20個點的最大獨立集方案數也可以求）

轉載于:https://www.cnblogs.com/Miracevin/p/10212265.html

總結

以上是生活随笔為你收集整理的[PKUWC2018]随机算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。