[USACO25FEB] Bessie's Function G 題解
題目傳送門
前言
本文為作者在參考多篇題解后覺得個人難以讀懂（主要原因?yàn)?s>作者太菜細(xì)節(jié)缺失），本文將通過配圖來解決無法讀懂這一問題。
題意簡述
給定 \(a_1,a_2,\cdots,a_n\) 以及修改每個 \(a_i\) 的代價 \(c_i\) ，希望通過對于每個 \(i\) ，都有 \(a_i=a_{a_i}\)
為了方便給出兩組樣例及配圖（藍(lán)字為有向邊終點(diǎn)的修改權(quán)值）
樣例1
輸入
5
2 4 4 5 3
1 1 1 1 1
輸出
3
圖
說明
將 \(a_1,a_4,a_5\) 分別改為 \(1,4,5\)后，我們得到
樣例2
輸入
8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9
輸出
7
圖
思路
基環(huán)樹版子題。
我們想到對于每組 \(a_i\) ，都建立一條從 \(a_i\) 到 \(i\) 的單向邊，并定義 \(a_i\) 為 \(i\) 的父親。
這樣一來，題目條件變?yōu)?，從一個點(diǎn) \(i\) 出發(fā)，其父親等于其祖父，換句話說，從一個點(diǎn) \(i\) 出發(fā)，逆箭頭走一步等于再走一步。
進(jìn)一步地， 要么 \(i\) 為自環(huán)，要么 \(a_i\)（\(i\) 的父親） 為自環(huán)。
顯然若 \(i\) 不滿足條件，將 \(a_i\) 修改為 \(i\) 最劃算。此處多題解都有證明，本處不再贅述。
由上圖，顯然這是一個外向基環(huán)樹森林（每個點(diǎn)有且僅有一條入邊），例如上圖在每個聯(lián)通塊的環(huán)中刪掉一條邊后，根節(jié)點(diǎn)有 \(1,2,(3\ \text{or}\ 5)\)。不妨設(shè)整張圖聯(lián)通，否則可以按不同聯(lián)通塊考慮。
基環(huán)樹典型操作：從環(huán)上選一邊特判，然后樹形dp剩下的兩顆樹。
（很玄學(xué)看不懂就別看了）
本題中，我們按照USACO的思路討論兩種情況（Subtask3和Subtask4）
Subtasks:
- Input 3: \(N≤20\)
- Inputs 4-9: \(a_i≥i\)
- Inputs 10-15: All \(a_i\) are distinct.
- Inputs 16-21: No additional constraints.
Subtask 3
Subtask3(Inputs4-9)中，每個 \(a_i\) 都大于等于 \(i\)，這保證了圖上除了自環(huán)不存在其他環(huán)[1]，
例如（USACO樣例太大，此處為作者自制）：
7
1 3 4 6 5 7 7
1 1 1 1 1 1 1
圖：
手玩幾組數(shù)據(jù)，我們注意到好吧圖畫出來還真挺顯然的，整張圖上所有連通塊不是自環(huán)就是“一顆樹”，但是樹的根節(jié)點(diǎn)是個自環(huán)。
對于所有自環(huán)的（如上圖就是 \(1,5,7\)，是的，基環(huán)樹上的自環(huán)也算），直接把 \(c_i\) 修改為 \(0\)，這樣方便后面累加修改值和樹形dp初始化時不用討論。
樹形dp
設(shè) \(dp_{i,0}\) 表示以 \(i\) 為根的子樹修改最小值，其中 \(i\) 不作修改。
設(shè) \(dp_{i,1}\) 表示以 \(i\) 為根的子樹修改最小值，其中 \(i\) 作修改，修改 \(a_i=i\)。
設(shè) \(u\) 的兒子集合為 \(\text{son}_u\)，
則我們有
- 若根不作修改，則根的兒子必須修改。因此
\(dp_{i,0}=\sum_{j\in{\text{son}_i}}dp_{j,1}\) - 若根作修改，則根的兒子可修可不修。因此
\(dp_{i,1}=c_i+\sum_{j\in{\text{son}_i}}\min\{dp_{j,0},dp_{j,1}\}\)
從根開始遞歸計(jì)算即可，注意要特判掉回到根節(jié)點(diǎn)的那條邊，防止重復(fù)計(jì)算。
最后的答案應(yīng)為 \(dp_{i,1}\)，因?yàn)楦?jié)點(diǎn)應(yīng)為一個自環(huán)，必須修改
代碼[2]：
int dfs(int u, int root)
{
dp[u][0] = 0;
dp[u][1] = c[u];
for (auto v: son[u]) {
if (v == root) continue;
dfs(v, root);
dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][0], dp[v][1]);
}
return dp[u][1];
}
Subtask 4
Subtask4(Input10-15)中，每個 \(a_i\) 都不同。
例如（此處同為作者自制）：
7
5 2 4 6 1 7 3
1 1 1 1 1 1 1
看圖：
顯然，整個圖上的聯(lián)通塊都是環(huán)。至于證明，留給讀者自證好了（逃）。
怎么解決環(huán)上問題呢？
首先特判自環(huán)。
剩下的環(huán)中，隨便選一條邊，然后就又雙叒叕★注意到★這誰注意得到啊喂在此邊的最終解決方案里，至少有一個點(diǎn)需為自環(huán)（FAQ：可是兩個點(diǎn)都為自環(huán)會浪費(fèi)吧 ANS：這個顯然樹形dp會在枚舉一端點(diǎn)時考慮到要不要修改另一端點(diǎn)的，因此此處不需考慮）。
那么，我們分別求出將此邊上兩端點(diǎn)修改為自環(huán)后，以其為根節(jié)點(diǎn)做樹形dp的代價，然后取最小值。
例如，對于上圖來說，3到7這一條邊，我們直接選擇3作根節(jié)點(diǎn)樹形dp（此處不需要修改是因?yàn)闃湫蝑p的深搜會自動考慮該情況的），得到結(jié)果等于對于（3->7->6->4）這一棵樹的dfs結(jié)果，也就是2，對于7我們得到同樣的結(jié)果，因此答案為2，累加到總答案上。
合并兩個Subtask
我們再來看這張圖：
其中含有的環(huán)可以用Subtask4的思路，隨便選一條邊，將其分開樹形dp:
自認(rèn)為此解比USACO官方的分類討論簡單點(diǎn)：
Full Solution:
We can combine the ideas from subtask 3 and 4
. For each component, locate the cycle using Floyd's Algorithm or DFS. If the cycle's length is 1, we can just use the solution from subtask 3
. Otherwise, use the idea from subtask 4 to convert the cycle into 2 instances of a rooted tree and solve each with subtask 3's solution.
大意：將環(huán)做法和樹做法融合。每次先用Floyd算法或深搜找環(huán)，然后判環(huán)的長度。若為1，直接樹形dp。否則，用Sub4的思想，斷環(huán)為兩樹，再套sub3的做法。
VS 我的改進(jìn)
對于每個聯(lián)通塊直接找環(huán)，然后不管環(huán)的長度直接斷環(huán)為鏈，如果是自環(huán)無影響，因?yàn)橐婚_始就初始化 c[自環(huán)點(diǎn)]=0 了
正確性證明：
如何保證這樣一定涵蓋了最優(yōu)解呢？
接下來純粹討論一下斷環(huán)為鏈的做法沒有遺漏的原因。
首先證明若環(huán)上一邊的兩點(diǎn)中皆無自環(huán)，則一定不合法。
證：設(shè)此邊起點(diǎn)為x，則x的父親即此邊終點(diǎn)，若兩者皆不是自環(huán)則根據(jù)定義不合法。Q.E.D.
然后，就討論兩點(diǎn)的修改這步，我們是分開討論，互不影響，沒有任何問題。由于保證了這條邊的合法性，所以得到
這條：此邊在圖中等于不存在，無需考慮。因此，原來的惡心基環(huán)樹變成了一個熱情的小哈可愛的樹，終于可以正常樹形dp辣
代碼
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, a[N];
vector<int> son[N]; // a[i]的反函數(shù)
int c[N]; // 修改a[i]的代價
int r1, r2; // a[r1] = r2
bool vst[N];
int dp[N][2]; // 子樹根為u，a[u]!=u(0)或a[u]==u(1)的最小代價
void find_loop(int u, int rt)
{
vst[u] = 1;
for (auto v: son[u]) {
if (v == rt) {
r1 = v;
r2 = u;
return ;
}
if (vst[v]) continue;
find_loop(v, rt);
}
}
int dfs(int u, int rt)
{
dp[u][0] = 0;
dp[u][1] = c[u];
for (auto v: son[u]) {
if (v == rt) continue;
dfs(v, rt);
dp[u][0] += dp[v][1]; // a[u]!=u,所以a[v]必須等于v
dp[u][1] += min(dp[v][0], dp[v][1]); // a[u]==u,所以a[v]可以等于v或不等于v
}
return dp[u][1];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
son[a[i]].push_back(i);
}
// 需滿足條件：對于任意i，a[a[i]]=a[i]
// 顯然將a[i]修改為i最劃算
for (int i = 1; i <= n; ++i) {
cin >> c[i];
// is indempotent
if (a[i] == i) c[i] = 0;
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
// for each component, locate the loop use dfs
if (vst[i]) continue;
r1 = r2 = 0;
find_loop(i, i);
if (r1 == 0) continue; // no loop
// choose any arbitrary edge in the loop
// break the edge and make the two vertices indempotent
int res1 = dfs(r1, r1);
int res2 = dfs(r2, r2);
ans += min(res1, res2);
}
cout << ans << '\n';
return 0;
}
后記
作者制作不易，如果您讀懂或覺得有幫助，請留個贊再走qwq
否則，也請您指出不足之處，謝謝！
證明：假設(shè)環(huán)由 \(a_{x_1}\rightarrow x_1=a_{x_2}\rightarrow x_2=a_{x_3}\rightarrow\cdots x_{k-1}=a_{x_k}\rightarrow x_k=a_{x_1}\) 構(gòu)成，則顯然 \(a_{x_1}\geq x_1=a_{x_2}\geq\cdots x_{k-1}=a_{k}\geq x_k=a_{x_1}\Longrightarrow x_1\geq x_k\geq x_1\Longrightarrow x_1=x_k\)，即此環(huán)上起點(diǎn)等于終點(diǎn)，所以此環(huán)長度為1，為自環(huán)。 ??
注意，本文除了最后貼上AC代碼，其余代碼都為作者寫博時手敲，不保證正確性。 ??
浙公網(wǎng)安備 33010602011771號