[BZOJ1596]电话网络

Problem

给你一棵树，可以在每个点上选择造塔或不造，每座塔可以覆盖这个节点和相邻节点，问覆盖整棵树的最小塔数。

Solution

看到这道题的第一眼，我就觉得是一题贪心题，但看见出题的时候分类在树形DP，于是就没仔细想贪心。

树形DP：f[u][0]表示u被其儿子覆盖，f[u][1]表示u上有塔，f[u][2]表示u被其父亲覆盖，转移显然

贪心：我们dfs到叶子节点时，尽量贪心覆盖它的父亲

Notice

树形DP的状态确实很难想到

Code

树形DP

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define sqz main

#define ll long long

#define reg register int

#define rep(i, a, b) for (reg i = a; i <= b; ++i)

#define per(i, a, b) for (reg i = a; i >= b; --i)

#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)

const int INF = 1e9, N = 10000;

const double eps = 1e-6, phi = acos(-1);

ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}

ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}

void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

struct node

{

    int vet, next;

}edge[2 * N + 5];

int ans = 0, flag[N + 5], num = 0, head[N + 5];

inline void add(const int &u, const int &v)

{

    edge[++num].vet = v, edge[num].next = head[u], head[u] = num;

    edge[++num].vet = u, edge[num].next = head[v], head[v] = num;

}

inline void dfs(reg u, reg fa)

{

    reg tt = 0;

    travel(i, u)

    {

        int v = edge[i].vet;

        if (v == fa) continue;

        dfs(v, u);

        if (flag[v]) tt = 1;

    }

    if (!tt && !flag[u] && !flag[fa])

    {

        ans++;

        flag[fa] = 1;

    }

}

int sqz()

{

    reg n = read();

    rep(i, 1, n - 1) add(read(), read());

    dfs(1, 0);

    write(ans); puts("");

    return 0;

}

贪心

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define sqz main

#define ll long long

#define reg register int

#define rep(i, a, b) for (reg i = a; i <= b; i++)

#define per(i, a, b) for (reg i = a; i >= b; i--)

#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)

const int INF = 1e8, N = 10000;

const double eps = 1e-6, phi = acos(-1);

ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}

ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}

void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

int f[N + 5][3], head[N + 5];

int num = 0;

struct node

{

	int vet, next;

}edge[2 * N + 5];

void add(int u, int v)

{

	edge[++num].vet = v;

	edge[num].next = head[u];

	head[u] = num;

	edge[++num].vet = u;

	edge[num].next = head[v];

	head[v] = num;

}

void dp(int u, int fa)

{

	int sum = 0;

	f[u][1] = 1, f[u][0] = INF;

	travel(i, u)

	{

		int v = edge[i].vet;

		if (v == fa) continue;

		dp(v, u);

		f[u][0] = min(f[u][0], f[v][1] - min(f[v][1], f[v][0]));

		f[u][1] += min(f[v][0], min(f[v][1], f[v][2]));

		f[u][2] += f[v][0];

		sum += min(f[v][0], f[v][1]);

	}

	f[u][0] += sum;

}

int sqz()

{

	int n = read();

	rep(i, 1, n - 1) add(read(), read());

	dp(1, 0);

	printf("%d\n", min(f[1][0], f[1][1]));

	return 0;

}