BZOJ 4472 salesman 题解
- 2020 年 4 月 5 日
- 笔记
题目
某售货员小T要到若干城镇去推销商品,由于该地区是交通不便的山区，任意两个城镇之间都只有唯一的可能经过其它城镇的路线。小T可以准确地估计出在每个城镇停留的净收益。这些净收益可能是负数，即推销商品的利润抵不上花费。由于交通不便，小T经过每个城镇都需要停留，在每个城镇的停留次数与在该地的净收益无关，因为很多费用不是计次收取的，而每个城镇对小T的商品需求也是相对固定的，停留一次后就饱和了。每个城镇为了强化治安，对外地人的最多停留次数有严格的规定。请你帮小T设计一个收益最大的巡回方案,即从家乡出发，在经过的每个城镇停留，最后回到家乡的旅行方案。你的程序只需输出最大收益，以及最优方案是否唯一。方案并不包括路线的细节，方案相同的标准是选择经过并停留的城镇是否相同。因为取消巡回也是一种方案，因此最大收益不会是负数。小T在家乡净收益是零，因为在家乡是本地人，家乡对小T当然没有停留次数的限制。
输入格式
输入的第一行是一个正整数(n(5<=n<=100000))，表示城镇数目。城镇以(1)到(n)的数命名。小T的家乡命名为(1)。第二行和第三行都包含以空格隔开的(n-1)个整数，第二行的第(i)个数表示在城镇(i+1)停留的净收益。第三行的第(i)个数表示城镇(i+1)规定的最大停留次数。所有的最大停留次数都不小于(2)。接下来的(n-1)行每行两个１到(n)的正整数(x)，(y)，之间以一个空格隔开，表示(x)，(y)之间有一条不经过其它城镇的双向道路。输入数据保证所有城镇是连通的。
输出格式
输出有两行，第一行包含一个自然数，表示巡回旅行的最大收益。如果该方案唯一，在第二行输出"solution is unique"，否则在第二行输出"solution is not unique"。
输入样例
9 -3 -4 2 4 -2 3 4 6 4 4 2 2 2 2 2 2 1 2 1 3 1 4 2 5 2 6 3 7 4 8 4 9 输出样例
9 solution is unique 样例解释
最佳路线包括城镇 1，2， 4， 5， 9
题解
任意两个城镇之间都只有唯一的可能经过其它城镇的路线,说明这一定是一棵树
第一问
这道题明显是树形动规,但加了一个限制条件,就是最大停留次数,联想树形动规时的形式,这个最大停留次数其实和能访问的子树个数有关系.
上图表示了一个DFS过程,其中2,3,4,5,6号都是子树,若将这些子树看成一个点,则DFS过程中经过的节点为
[1] 2 [1] 2 [1] 4 [1] 5 [1] 6 [1] 注意其中的根节点1,出现了6次,本题中就是停留了6次,而1号节点有5棵子树,可以发现,若i节点最大停留次数为(limit[x]),则DFS中最多能访问(limit[x]-1)棵子树
这些子树中对根节点dp的贡献不同,我们当然要选择其中最大的,所以排一下序,选其中前(limit[x]-1)棵子树来更新根节点的dp值.
注意,(limit[x]-1)也存在大于子树个数的情况,所以实际操作的时候要取(limit[x])和字数个数的最小值作为更新根节点的子树数量,由于净收益可能是负数,所以更新的时候发现是负数立刻停止即可.
所以遍历子树(已排序)时候,条件为
soni < min(limit[root] - 1, sontot) && dp[sonn[soni + 1]] >= 0 其中,soni为当前循环遍历的子树时的循环变量(注意不时子树根节点编号),root为根节点编号,sontot为子树的数量,sonn数组保存子树的根节点编号,sonn[soni+1]为这次循环的子树编号(因为soni在循环内自增1)
还有一个条件
家乡对小T当然没有停留次数的限制
也就是整棵树的根节点无限制次数,那么只需要在DFS之前将根节点的limit值赋值为无限大即可
第二问
显然,根节点方案是否唯一首先要看其子树,如果有任意一棵更新了根节点dp值得子树的方案不唯一,根节点的方案显然也不唯一.
除此之外,还有存在子树方案唯一但根节点选取子树的方案不唯一的情况.
遍历子树的时候,将 子树方案是否唯一的值 和 根节点选取子树的方案是否唯一 的值进行或运算(只要有一个为真,结果就为真),得到的结果就是这棵树的方案是否唯一,最后输出即可.
那么怎么判断根节点选取子树的方案是否唯一呢,有两种情况:
- 相同值引起的不唯一
假设排好序后的子树dp值为10 9 8 7 6 6 5 4 3 2 1,而你只能选5个(limit值为6),显然你选择的是10 9 8 7 6,但是仔细观察,你会发现还有一个相同的6,那么我能不能抛弃第一个6选择第二个6呢?当然可以,那么,这就有了两种选择办法([10] [9] [8] [7] [6] 6 5 4 3 2 1和[10] [9] [8] [7] 6 [6] 5 4 3 2 1)
- dp值为0引起的不唯一
假设排好序后的子树dp值为10 9 8 7 6 0,而你只能选5个(limit值为6),你可以选择10 9 8 7 6,也可以选择10 9 8 7 6 0,这两种方案更新的值都是一样的.
出现这两种情况时,直接将这棵树方案是否唯一的赋值为真即可
代码
#include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N = 100000; struct edge { int i, next; } edges[2 * N + 5]; int head[N + 5], tot, n, w[N + 5], limit[N + 5], dp[N + 5], ansn[N + 5],sonn[N + 5]; void add(int u, int v) { edges[++tot].i = v; edges[tot].next = head[u]; head[u] = tot; } bool cmp(int a, int b) { return dp[a] > dp[b]; } void dfs(int root, int f) { dp[root] = w[root]; int sontot = 0, soni = 0; for (int i = head[root]; i; i = edges[i].next) if (edges[i].i != f) dfs(edges[i].i, root); for (int i = head[root]; i; i = edges[i].next) if (edges[i].i != f) sonn[++sontot] = edges[i].i; sort(sonn + 1, sonn + 1 + sontot, cmp); while (soni < min(limit[root] - 1, sontot) && dp[sonn[soni + 1]] >= 0) dp[root] += dp[sonn[++soni]], ansn[root] |= ansn[sonn[soni]];//按位或 if (soni < sontot && soni > 0 && dp[sonn[soni]] == dp[sonn[soni + 1]] || dp[sonn[soni]] == 0 && soni > 0)//两种情况,注意边界 ansn[root] = 1; } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) scanf("%d", &w[i + 1]); for (int i = 1; i < n; i++) scanf("%d", &limit[i + 1]); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); } limit[1] = n + 1;//在家乡没有停留限制 dfs(1, 0); printf("%dn%s", dp[1], ansn[1] ? "solution is not unique" : "solution is unique"); return 0; } 
