[Usaco2008 Jan]电话网络 贪心 or 树形DP

时间：2022-12-04 00:50:40

Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。 不过，为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上 无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N 顺次编号。 所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1 <= A <= N; 1 <= B <= N; A != B)，都可以找到一个以A开头以B结尾的草地序列，并且序列 中相邻的编号所代表的草地相邻。无线电通讯塔只能建在草地上，一座塔的服务 范围为它所在的那块草地，以及与那块草地相邻的所有草地。 请你帮FJ计算一下，为了建立能覆盖到所有草地的通信系统，他最少要建 多少座无线电通讯塔。




这题貌似以前见过。

有两种做法

第一种是贪心

先DFS将一个无根树变为有根树，并计算出每个结点的深度

这时可以进行贪心了。

按照深度从高到低来枚举结点，对于一个结点，只需在其父亲结点上放置信号塔，然后将其周围的点覆盖。


#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#define MAXN 11111
#define MAXM 211111
#define PI acos(-1.0)
#define eps 1e-8
#define INF 1000000001
using namespace std;
int n;
int fa[MAXN];
vector<int> g[MAXN], dg[MAXN];
int cover[MAXN];
void dfs(int u, int dep)
{
    dg[dep].push_back(u);
    int sz = g[u].size();
    for(int i = 0; i < sz; i++)
    {
        int v = g[u][i];
        if(v == fa[u]) continue;
        fa[v] = u;
        dfs(v, dep + 1);
    }
}
void color(int u, int f)
{
    cover[u] = 1;
    int sz = g[u].size();
    for(int i = 0; i < sz; i++)
    {
        int v = g[u][i];
        if(v == f) continue;
        cover[v] = 1;
    }
}
int main()
{
    int u, v;
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    int ans = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        int sz = dg[i].size();
        for(int j = 0; j < sz; j++)
        {
            int u = dg[i][j];
            if(cover[u]) continue;
            int v = fa[u];
            ans++;
            color(v, 0);
        }
    }
    printf("%d\n", ans);
    return 0;
}

然后本题的另一种做法就是树形DP

dp[i][0] 表示i结点为根的子树被覆盖并且 i结点上有塔

dp[i][1] 表示i结点为根的子树被覆盖并且i结点上没有塔

dp[i][2]表示i结点为根的子树除了i全被覆盖了


那么对于dp[i][0] 因为i肯定要放塔

所以dp[i][0] = sigma(min(dp[j][0], dp[j][1], dp[j][2]))  j 是i的儿子


dp[i][2]的话，显然因为i不能被覆盖，所以其儿子上也不能放塔

dp[i][2] = sigma(dp[j][1])  j是i的儿子


dp[i][1]就略有点麻烦了。

就要保证儿子中必须至少有一个放塔的。

那么我们先取 dp[i][1] = sigma(min(dp[j][0], dp[j][1]))

然后如果里面都是没放塔的，显然要找一个儿子放塔


#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#define MAXN 11111
#define MAXM 211111
#define PI acos(-1.0)
#define eps 1e-8
#define INF 100000001
using namespace std;
int n;
int fa[MAXN];
vector<int> g[MAXN];
int dp[MAXN][3];
void dfs(int u, int fa)
{
    int sz = g[u].size();
    int sum = 0;
    dp[u][0] = 1;
    for(int i = 0; i < sz; i++)
    {
        int v = g[u][i];
        if(v == fa) continue;
        dfs(v, u);
        dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
        sum += min(dp[v][0], dp[v][1]);
        dp[u][2] += dp[v][1];
    }
    dp[u][1] = INF;
    if(sz == 1 && u != 1) return;
    for(int i = 0; i < sz; i++)
    {
        int v = g[u][i];
        if(v == fa) continue;
        dp[u][1] = min(dp[u][1], dp[v][0] + sum - min(dp[v][0], dp[v][1]));
    }
}
int main()
{
    int u, v;
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    printf("%d\n", min(dp[1][0], dp[1][1]));
    return 0;
}


标签：

相关文章