题目内容

P6082

大意:给定一棵 n 个点的树,有点权,从 1 号点开始一次旅行,最后回到 1 号点。每到达一个点,就能获得等于该点点权的收益。每个点都有进入该点的次数限制,且每个点的收益只获得一次。求最大收益以及方案是否唯一。

解题思路

不难发现,这道题满足最优子结构,一棵子树的答案可由这棵子树的子树合并而来。

注意到进入限制这个性质,到达这个点进入了一次,去到每一棵子树再回来又是进入这个点一次,所以实际上我们只能访问这个点的 限制次数减一 棵子树。

而为了保证最优,需要使用贪心思想,当将一个节点的所有子树的信息处理完之后,将其从大到小排序,取前面的限制次数减一个并加起来(当然如果加到负数就肯定不加了)。

至于解的唯一性,注意到如果一个子树下的某个子树的解不唯一,那么这个子树的解肯定也不唯一。以及如果对于他的一棵子树,这个子树的答案为 0,则走与不走这个子树的效果是相同的,答案就会不唯一。还有,如果最后一个选的子树 a 的答案与下一个待选子树 b 的答案相同,说明可以选 a 也可以选 b,效果都是一样的,也会产生多解。

代码如下:

#include <utility>
#include <cstdio>
#include <cctype>
#include <queue>

using std::priority_queue;
using std::make_pair;
using std::vector;
using std::pair;

const int maxn=1e5+5;
int n,money[maxn],stop[maxn];
int f[maxn][2];

vector<int> g[maxn];

inline void ins(int from,int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
    return;
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(g[now].size()==1)//这是判断是否为叶子节点的
    {
        f[now][0]=money[now];
        return;
    }
    priority_queue<pair<int,int> > q;//排序用
    for(int i=0;i<g[now].size();i++)//访问下面的节点
    {
        if(g[now][i]!=fa)
        {
            dfs(g[now][i],now);//继续递归
            q.push(make_pair(f[g[now][i]][0],g[now][i]));//并且加入队列
        }
    }
    int lastChosen;
    for(int i=1; (!q.empty()) && (now==1 ? 1 : i<stop[now]);i++)
    {
        int to=q.top().second,val=q.top().first;
        if(val<0)//如果现在这棵子树已经小于 0 了,说明会产生负贡献,直接舍弃
            break;
        if(val==0)//有多解
            f[now][1]=1;
        f[now][0] += val;
        lastChosen=val;
        f[now][1] |= f[to][1];//下面的答案有多解的话也会产生多解
        q.pop();
    }
    f[now][0]+=money[now];
    if(q.size() && q.top().first==lastChosen)//如果下一个备选答案与上一个的相同,则有多解
        f[now][1]=1;
    return;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
        money[i+1]=read();
    for(int i=1;i<n;i++)
        stop[i+1]=read();
    int from,to;
    for(int i=1;i<n;i++)
    {
        from=read(),to=read();
        ins(from,to);
    }
    dfs(1,0);
    printf("%d\n",f[1][0]);
    if(f[1][1])
        printf("solution is not unique\n");
    else
        printf("solution is unique\n");
    return 0;
}
最后修改日期:2020年4月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。