Strategic game

题目大意

对于任意一条边，其都只有两种被覆盖的可能:
1.被上面的节点(父节点)覆盖
2.被下面的节点(子节点)覆盖
故容易推出状态表示和方程
dp[i][j]:以i为根的子树的所有边被覆盖且i的状态为j的所有方案的数量最小值
(j = 0表示i不放士兵，j = 0为i放士兵)
转移方程
dp[i][0] = ∑(dp[son][1])
dp[i][1] = ∑(min(dp[son][1],dp[son][0]) + 1;
边界设置:对于叶子节点 dp[i][0] = 0, dp[i][1] = 1; 从定义出发
AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio> 
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>
#define vpii vector<pii> 
#define mp(a, b) make_pair(a, b)
#define pll pair <ll, ll>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
inline int lowbit(int x) {return x & -x;} 
template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
inline int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename t> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename t> inline void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 4e3 + 10, mod = 1e9 + 7;
int n, m;
int h[N], nex[N], v[N], idx;
void add(int a, int b) {
    v[idx] = b; nex[idx] = h[a]; h[a] = idx ++ ;
}

int f[N][5], st[N];
void init() {
    mset(h, -1); mset(f, 0); mset(st, 0); idx = 0;
}

void dp(int u) {
    bool fg = 0;
    for(int i = h[u]; ~i; i = nex[i]) {
        int j = v[i];
        fg = 1;
        dp(j);
        f[u][0] += f[j][1];
        f[u][1] += min(f[j][0], f[j][1]);
    }
    f[u][1] += 1;
    if(!fg) {
        f[u][0] = 0; f[u][1] = 1;
    }
}

int main() {
    while(cin >> n) {
        init();
        rep(i, 1, n) {
            int a, num, b; char t;
            cin >> a >> t >> t >> num >> t;
            rep(j, 1, num) {
                cin >> b; add(a, b); st[b] = 1;
            }
        }
        int root = 0;
        while(st[root]) root ++ ;
        dp(root);
        cout << min(f[root][1], f[root][0]) << endl;
    }

    return 0;
}

Cell Phone Network (https://ac.nowcoder.com/acm/problem/24953)

与 Strategic game的对比

树的最小支配集问题 与 树的最小点覆盖的对比

附上雨巨的画图解释

研究对象不同导致状态转移的不同，前者研究的是覆盖住所有的点，树的任意一个点都可能被自身，儿子，父亲三者之一所覆盖，故状态转移有三种可能，后者研究的是覆盖所有的边，任意的边只可能连接两个节点，故状态转移只能来自二者之一</ll,></int,>