算法提高课汇总

算法思路

本题是 AcWing 323. 战略游戏 的进阶版.

• 战略游戏: 每条边两端至少有一个点放置士兵, 每次只需要考虑节点$u$与其子节点之间的关系.

• 皇宫看守: 对于每个点, 至少其自身或与其相连的点被放置士兵, 此时$u$不仅可能被自身或者其
  子节点观察, 被其父节点观察也需要考虑进去.

状态机

状态表示 $dp(u, j), j = \lbrace 0, 1, 2\rbrace$

• 集合: 以$u$为根且$u$的状态为$j$的所有放置方案. 其中:
  • $j = 0$: $u$上不放置士兵且被其父节点观察(父节点放置士兵).
  • $j = 1$: $u$上不防止士兵且被其子节点观察(至少一个子节点放置士兵).
  • $j = 2$: $u$上放置士兵.
    $\;$
• 属性: Min 放置士兵对应点权重之和

状态计算

分别考虑$u$不同状态与其子节点状态关系:

• $dp(u, 0)$: $u$上不放置士兵且已经被其父节点观察, 所以其子节点不能被$u$观察, 其他两个状态均合法.
  $dp(u, 0) = \sum min\lbrace dp(son, 1), dp(son, 2)\rbrace$

• $dp(u, 2)$: $u$上放置士兵, 其子节点状态任意.
  $dp(u, 0) = \sum min\lbrace dp(son, 0), dp(son, 1), dp(son, 2)\rbrace + w(u)$

• $dp(u, 1)$: $u$上不放置士兵且被子节点观察, 则至少有一个子节点放置士兵, 其他节点可放置或可被其
  子节点观察. 为使得$dp(u, 1)$最小, 我们只固定一个子节点$k$必须放置士兵.
  $dp(u, 1) = dp(k, 2) + \sum_{son\not= k} min\lbrace dp(son, 1), dp(son, 2)\rbrace$
  $= dp(k, 2) + \sum_{son\not= k} min\lbrace dp(son, 1), dp(son, 2)\rbrace + min\lbrace dp(k, 1), dp(k, 2)\rbrace - min\lbrace dp(k, 1), dp(k, 2)\rbrace$
  $ = dp(k, 2) + \sum min\lbrace dp(son, 1), dp(son, 2)\rbrace - min\lbrace dp(k, 1), dp(k, 2)\rbrace$
  $ = dp(k, 2) + dp(u, 0) - min\lbrace dp(k, 1), dp(k, 2)\rbrace$.

代码实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1510, M = N, INF = 1e9;

int n;
int h[N], e[M], ne[M], idx;
int w[N], dp[N][3];
bool st[N];

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++ ;
}

void dfs(int u)
{
    dp[u][2] = w[u];
    for ( int i = h[u]; ~i; i = ne[i] )
    {
        int v = e[i];
        dfs(v); //自底向上
        dp[u][0] += min( dp[v][1], dp[v][2] );
        dp[u][2] += min( min(dp[v][0], dp[v][1]), dp[v][2] );
    }

    dp[u][1] = INF;
    for ( int i = h[u]; ~i; i = ne[i] )
    {
        int v = e[i];
        int val = dp[u][0] - min( dp[v][1], dp[v][2] ) + dp[v][2];
        dp[u][1] = min( dp[u][1], val );
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for ( int i = 1; i <= n; i ++ )
    {
        int u, cost, cnt;
        cin >> u >> cost >> cnt;

        w[u] = cost;
        while ( cnt -- )
        {
            int v;
            cin >> v;
            add(u, v); st[v] = true;
        }
    }

    int root = 1;
    while ( st[root] )  root ++ ;

    dfs( root );
    cout << min( dp[root][1], dp[root][2] ) << endl;

    return 0;
}