皇宫看守 一本通 （最小支配集 树形dp）

题目链接

思路：这题刚开始以为和战略游戏这题一样，但是试了发现不对劲，战略游戏是最大独立集，相连的两个点不可能同时取，但是这题是可以的。

1、建图，这题需要找一下root根节点
2、dp过程：
//dp[rt][0]:以rt为根的树中，rt不选，rt被父亲支配状态下的最优解
//dp[rt][1]:以rt为根的树中，rt不选，rt被孩子支配状态下的最优解
//dp[rt][2]:以rt为根的树中，rt自己选取状态下的最优解

转移方程：
dp[rt][0]=Σ (min (dp[child][1] , dp[child][2] ) （此时child无法被rt支配）

dp[rt][2]=val[rt]+ Σ （min( dp[child][1] , dp[child][0] , dp[child][2] )）(child三种都可能)

dp[rt][1] :不能简单=Σ min(dp[child][1],dp[child][2]) -----这样可能导致dp[rt][1]全部由dp[child][1]转移而来 即：孩子节点自己全没选，被孙子节点选取了， 而我们又必须存在一个孩子是选了自己的，只有这样才能保证rt也被选了。

dp[rt][1]的解决办法有两种：
首先是暴力解法 ： 枚举每一个孩子节点，取它的dp[child][2]，int temp=dp[child][2],然后temp+=Σ min ( dp[child] [1] , dp[child] [2]) （child为其它孩子节点）

最终把每种枚举情况下的temp，取min就可以 ，由于这题数据比较少，暴力可以AC

第二种方法需要一点点数学思维，我们假设

Σ min(dp[child][1],dp[child][2]) 中每个数据取到的都是dp[child][1]的值，（取到了后者那么肯定满足条件了233），但是由于我们至少需要1个child取到dp[child[2]，所以我们可以把其中一个dp[child][1]的值变成dp[child][2]的值，那么很明显，我们需要把这个转换的代价降到最低， 所以我们取满足dp[child][2]和dp[child][1] 相差最小的那组数据，就ok了 。

故，dp[rt][1]=d+Σ min(dp[child][1],dp[child][2])
d=min(dp[child][2]-min(dp[child][2],dp[child][1])
当存在一个child 的 dp[child][2] 小于等于 dp[child][1] ，d就是0
当不存在，d就是二者之差，也就是上述分析中的最小转换代价

先上第二种方法的代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<math.h>
#include<set>
using namespace std;
#define LL long long
#define ULL unsigned long long
const int INF=0x3f3f3f3f;
const double eps=1e-5;
const int maxn=5e3+10;

struct
{
    int to,next;
}edge[maxn];//前向星存图
int head[maxn];
int cnt=1;
int n;
void add(int v,int to)
{
    edge[cnt].to=to;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
int father[maxn];
int dp[maxn][3];
int val[maxn];
//dp[rt][0]:以rt为根的树中，rt不选，被父亲支配状态下的最优解
//dp[rt][1]:以rt为根的树中，rt不选，被孩子支配状态下的最优解
//dp[rt][2]:以rt为根的树中，rt自己选取状态下的最优解
void dfs(int rt)
{
    int d=INF;
    for(int j=head[rt];j;j=edge[j].next)
    {
        int to=edge[j].to;
        dfs(to);//完成一个孩子节点 就更新一次父节点
        dp[rt][0]+=min(dp[to][1],dp[to][2]);
        dp[rt][2]+=min(dp[to][2],min(dp[to][0],dp[to][1]));
        d=min(d,dp[to][2]-min(dp[to][2],dp[to][1]));//对每个child都维护一次d的值
        dp[rt][1]+=min(dp[to][1],dp[to][2]);
    }
    dp[rt][1]+=d;
    dp[rt][2]+=val[rt];//选本身
}
int main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    scanf("%d",&n);
    fill(father,father+maxn,-1);
    int root;
    for(int i=1;i<=n;i++)
    {
        int v,m;
        scanf("%d",&v);
        root=v;
        scanf("%d %d",val+v,&m);
        for(int j=1;j<=m;j++)
        {
            int u;
            scanf("%d",&u);
            father[u]=v;
            add(v,u);
        }
    }
    while(father[root]!=-1) root=father[root];   
    dfs(root);
    printf("%d\n",min(dp[root][1],dp[root][2]));
//    system("pause");
    return 0;
}

暴力解法代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<math.h>
#include<set>
using namespace std;
#define LL long long
#define ULL unsigned long long
const int INF=0x3f3f3f3f;
const double eps=1e-5;
const int maxn=5e3+10;
//题意：给定一棵树，每个点都有权值，选定某个点，则于其直接相连的点都被选择，问选完所有顶点的最小权值花费
//最小支配集，对于每个顶点，需要考虑三个情况：1、被父亲节点支配 2、被孩子节点支配 3、自己支配自己
struct
{
    int to,next;
}edge[maxn];//前向星存图
int head[maxn];
int cnt=1;
int n;
void add(int v,int to)
{
    edge[cnt].to=to;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
int father[maxn];
int dp[maxn][3];
int val[maxn];
//dp[rt][0]:以rt为根的树中，rt不选，被父亲支配状态下的最优解
//dp[rt][1]:以rt为根的树中，rt不选，被孩子支配状态下的最优解
//dp[rt][2]:以rt为根的树中，rt自己选取状态下的最优解
void dfs(int rt)
{
    for(int j=head[rt];j;j=edge[j].next)
    {
        int to=edge[j].to;
        dfs(to);//完成一个孩子节点 就更新一次父节点
        dp[rt][0]+=min(dp[to][1],dp[to][2]);
        dp[rt][2]+=min(dp[to][2],min(dp[to][0],dp[to][1]));
    }
    dp[rt][2]+=val[rt];
    dp[rt][1]=INF;//这种情况下，需要每个孩子都求完了，才能求dp[rt][1]
    for(int j=head[rt];j;j=edge[j].next)//枚举 选自身的孩子节点
    {
        int to=edge[j].to;
        int temp=dp[to][2];//选自身
        for(int k=head[rt];k;k=edge[k].next)//枚举其它孩子节点
        {
            int other=edge[k].to;
            if(other==to) continue;
            temp+=min(dp[other][2],dp[other][1]);
        }
        dp[rt][1]=min(temp,dp[rt][1]);//维护
    }
}
int main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    scanf("%d",&n);
    fill(father,father+maxn,-1);
    int root;
    for(int i=1;i<=n;i++)
    {
        int v,m;
        scanf("%d",&v);
        root=v;
        scanf("%d %d",val+v,&m);
        for(int j=1;j<=m;j++)
        {
            int u;
            scanf("%d",&u);
            father[u]=v;
            add(v,u);
        }
    }
    while(father[root]!=-1) root=father[root];   
    dfs(root);
    printf("%d\n",min(dp[root][1],dp[root][2]));
    system("pause");
    return 0;
}

本文地址：https://blog.csdn.net/qq_46030630/article/details/108576366