Luogu2016 战略游戏 / UVA1292 Strategic game

发布于 2019-10-31  116 次阅读


Luogu2016

UVA1292 Strategic game

双倍经验,重题请做P2016

很明显的一道树形DP,可以分两种情况讨论。

第一种,在当前点 u 不放置一个士兵,那么它的子树全部得放,则:f[u][0] = \sum_{v \in son(u)} f[v][1]

第二种,如果放置一个士兵,它子树中的节点可放可不放,则:f[u][1] = \sum_{v\in son(u)} min(f[v][1], f[v][0])

最后答案为 root 节点的放置个数,即:min(f[1][0], f[1][1])

习惯于 1 作为根节点,故读入时全部节点编号+1

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1500 + 5;

int n, num;
int head[SIZE], f[SIZE][2];

struct node {
    int to, Next;
} edge[SIZE << 1];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int u, int fa)
{
    f[u][1] = 1, f[u][0] = 0;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa) continue;
        DFS(v, u);
        f[u][0] += f[v][1];
        f[u][1] += std::min(f[v][0], f[v][1]);
    }
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++) {
        int u = read() + 1, k = read();
        for (int j = 1; j <= k; j++) {
            int v = read() + 1;
            Addedge(u, v);
            Addedge(v, u);
        }
    }
    DFS(1, 0);
    printf("%d", std::min(f[1][0], f[1][1]));
    return 0;
}

苟利国家生死以,岂因祸福避趋之.