轉自：https://www.cnblogs.com/Ash-ly/p/5783877.html

一:最小支配集

考慮最小支配集,每個點有兩種狀態,即屬于支配集合或者不屬于支配集合,其中不屬于支配集合時此點還需要被覆蓋,被覆蓋也有兩種狀態,即被子節點覆蓋或者被父節點覆蓋.總結起來就是三種狀態,現對這三種狀態定義如下:

1):dp[i][0],表示點 i 屬于支配集合,并且以點 i 為根的子樹都被覆蓋了的情況下支配集中所包含最少點的個數.

2):dp[i][1],表示點 i 不屬于支配集合,且以 i 為根的子樹都被覆蓋,且 i 被其中不少于一個子節點覆蓋的情況下支配集所包含最少點的個數.

3):dp[i][2],表示點 i 不屬于支配集合,且以 i 為根的子樹都被覆蓋,且 i 沒被子節點覆蓋的情況下支配集中所包含最少點的個數.即 i 將被父節點覆蓋.

對于第一種狀態,dp[i][0]含義為點 i 屬于支配集合,那么依次取每個兒子節點三種狀態中的最小值,再把取得的最小值全部加起來再加 1,就是dp[i][0]的值了.即只要每個以 i 的兒子為根的子樹都被覆蓋,再加上當前點 i,所需要的最少的點的個數,DP轉移方程如下:

dp[i][0] = 1 + ∑(u 取 i 的子節點)min(dp[u][0], dp[u][1], dp[u][2])

對于第三種狀態,dp[i][2]含義為點 i 不屬于支配集合,且 i 被其父節點覆蓋.那么說明點 i 和點 i 的兒子節點都不屬于支配集合,所以點 i 的第三種狀態之和其兒子節點的第二種狀態有關,方程為:

dp[i][2] =?∑(u 取 i 的子節點)dp[u][1]

對于第二種狀態,略有些復雜.首先如果點 i 沒有子節點那么 dp[i][1]應該初始化為 INF;否則為了保證它的每個以 i 的兒子為根的子樹被覆蓋,那么要取每個兒子節點的前兩種狀態的最小值之和,因為此時點 i 不屬于支配集,不能支配其子節點,所以子節點必須已經被支配,與子節點的第三種狀態無關.如果當前所選狀態中每個兒子都沒被選擇進入支配集,即在每個兒子的前兩種狀態中,第一種狀態都不是所需點最小的,那么為了滿足第二種狀態的定義(因為點 i 的第二種狀態必須被其子節點覆蓋,即其子節點必須有一個屬于支配集,如果此時沒有,就必須強制使一個子節點的狀態為狀態一),需要重新選擇點 i 的一個兒子節點為第一種狀態,這時取花費最少的一個點,即取min(dp[u][0] - dp[u][1])的兒子節點 u,強制取其第一種狀態,其他的兒子節點取第二種狀態,DP轉移方程為:

if(i 沒有子節點)?? dp[i][1] = INF

else?????????????????? dp[i][1] =?∑(u 取 i 的子節點)min(dp[u][0], dp[u][1]) + inc

其中對于 inc 有:

if(上面式子中的?∑(u 取 i 的子節點)min(dp[u][0], dp[u][1]) 中包含某個 dp[u][0], 即存在一個所選的最小值為狀態一的兒子節點) inc = 0

else??? inc = min(dp[u][0] - dp[u][1])? (其中 u 取點 i 的兒子節點)

代碼：

void DP(int u, int p) {// p 為 u 的父節點dp[u][2] = 0;dp[u][0] = 1;bool s = false;int sum = 0, inc = INF;for(int k = head[u]; k != -1; k = edge[k].next) {int to = edge[k].to;if(to == p) continue;DP(to, u);dp[u][0] += min(dp[to][0], min(dp[to][1], dp[to][2]));if(dp[to][0] <= dp[to][1]) {sum += dp[to][0];s = true;}else {sum += dp[to][1];inc = min(inc, dp[to][0] - dp[to][1]);}if(dp[to][1] != INF && dp[u][2] != INF) dp[u][2] += dp[to][1];else dp[u][2] = INF;}if(inc == INF && !s) dp[u][1] = INF;else {dp[u][1] = sum;if(!s) dp[u][1] += inc;} }

二:最小點覆蓋

對于最小點覆蓋,每個點只有兩種狀態,即屬于點覆蓋或者不屬于點覆蓋:

1):dp[i][0]表示點 i 屬于點覆蓋,并且以點 i 為根的子樹中所連接的邊都被覆蓋的情況下點覆蓋集中所包含最少點的個數.

2):dp[i][1]表示點 i 不屬于點覆蓋,且以點 i 為根的子樹中所連接的邊都被覆蓋的情況下點覆蓋集中所包含最少點的個數.

對于第一種狀態dp[i][0],等于每個兒子節點的兩種狀態的最小值之和加 1,DP轉移方程如下:

dp[i][0] = 1 + ∑(u 取 i 的子節點)min(dp[u][0], dp[u][1])

對于第二種狀態dp[i][1],要求所有與 i 連接的邊都被覆蓋,但是點 i 不屬于點覆蓋,那么點 i 的所有子節點就必須屬于點覆蓋,即對于點 i 的第二種狀態與所有子節點的第一種狀態有關,在數值上等于所有子節點第一種狀態的和.DP轉移方程如下:

dp[i][1] = ∑(u 取 i 的子節點)dp[u][0]

代碼：

void DP(int u, int p) {// p 為 u 的父節點dp[u][0] = 1;dp[u][1] = 0;for(int k = head[u]; k != -1; k = edge[k].next) {int to = edge[k].to;if(to == p) continue;DP(to, u);dp[u][0] += min(dp[to][0], dp[to][1]);dp[u][1] += dp[to][0];} }

三:最大獨立集

對于最大獨立集,每個點也只有兩種狀態,即屬于點 i 屬于獨立集或者不屬于獨立集兩種情況:

1):dp[i][0]表示點 i 屬于獨立集的情況下,最大獨立集中點的個數.

2):dp[i][1]表示點 i 不屬于獨立集的情況下.最大獨立集中點的個數.

對于第一種狀態dp[i][0],由于 i 點屬于獨立集,所以它的子節點都不能屬于獨立集,所以對于點 i 的第一種狀態,只和它的子節點的第二種狀態有關.等于其所有子節點的第二種狀態的值加 1,DP轉移方程如下:

dp[i][0] = 1 + ∑(u 取 i 的子節點)?dp[u][1]

對于第二種狀態dp[i][1],由于點 i 不屬于獨立集,所以子節點可以屬于獨立解,也可以不屬于獨立集,所取得子節點狀態應該為數值較大的那個狀態,DP轉移方程:

dp[i][1] = ∑(u 取 i 的子節點)max(dp[u][0], dp[u][1])

代碼：

void DP(int u, int p) {// p 為 u 的父節點dp[u][0] = 1;dp[u][1] = 0;for(int k = head[u]; k != -1; k = edge[k].next) {int to = edge[k].to;if(to == p) continue;DP(to, u);dp[u][0] += dp[to][1];dp[u][1] += max(dp[to][0], dp[to][1]);} }

參考文獻《圖論及應用》,以及部分網上的資料.

總結

以上是生活随笔為你收集整理的树形DP求树的最小支配集,最小点覆盖,最大独立集的全部內容，希望文章能夠幫你解決所遇到的問題。

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