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; } 
