算法提高课汇总

算法思路

题目要求每条边两端至少有一个点, 与 AcWing 285. 没有上司的舞会 构成对称关系:

• 没有上司的舞会: 每条边最多一个点, 求所有方案点权重之和最大值.

• 战略游戏: 每条边最少一个点, 求所有方案点权重(1)之和最小值.

我们可以按照相同思路求解.

状态机

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

• 集合: 以节点$u$为根节点, 状态为$j$的所有方案. 其中$j = 0$表示$u$上不放置士兵, $1$表示放置士兵.

• 属性: Min

状态计算

自底向上求解, 每次只需要考虑当前节点与其子节点的关系.

• $dp(u, 0)$: $u$上不放置士兵, 则其子节点$v$上必须放士兵, 以保证边$(u, v)$有士兵观察. $dp(u, 0) = \sum dp(v, 1)$.

• $dp(u, 1)$: $u$上放置士兵, 则其子节点放不放置士兵均可. $dp(u, 0) = \sum min\lbrace dp(v, 0), dp(v, 1)\rbrace$.

代码实现

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

using namespace std;

const int N = 1510, M = N;

int n;
int h[N], e[M], ne[M], idx;
int dp[N][2];
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][0] = 0, dp[u][1] = 1;
    for ( int i = h[u]; ~i; i = ne[i] )
    {
        int v = e[i];
        dfs(v); //自底向上
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int main()
{
    while ( scanf("%d", &n) != EOF )
    {
        idx = 0;
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        for ( int i = 1; i <= n; i ++ )
        {
            int u, cnt;
            scanf("%d:(%d)", &u, &cnt); //格式化输入 
            while ( cnt -- )
            {
                int v;
                scanf("%d", &v);
                add(u, v); st[v] = true;
            }
        }

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

        dfs(root);
        cout << min(dp[root][0], dp[root][1]) << endl;
    }
    return 0;
}