F. Selling a Menagerie
You are the owner of a menagerie consisting of $n$ animals numbered from $1$ to $n$. However, maintaining the menagerie is quite expensive, so you have decided to sell it!
It is known that each animal is afraid of exactly one other animal. More precisely, animal $i$ is afraid of animal $a_i$ ($a_i \neq i$). Also, the cost of each animal is known, for animal $i$ it is equal to $c_i$.
You will sell all your animals in some fixed order. Formally, you will need to choose some permutation$^\dagger$ $p_1, p_2, \ldots, p_n$, and sell animal $p_1$ first, then animal $p_2$, and so on, selling animal $p_n$ last.
When you sell animal $i$, there are two possible outcomes:
- If animal $a_i$ was sold before animal $i$, you receive $c_i$ money for selling animal $i$.
- If animal $a_i$ was not sold before animal $i$, you receive $2 \cdot c_i$ money for selling animal $i$. (Surprisingly, animals that are currently afraid are more valuable).
Your task is to choose the order of selling the animals in order to maximize the total profit.
For example, if $a = [3, 4, 4, 1, 3]$, $c = [3, 4, 5, 6, 7]$, and the permutation you choose is $[4, 2, 5, 1, 3]$, then:
- The first animal to be sold is animal $4$. Animal $a_4 = 1$ was not sold before, so you receive $2 \cdot c_4 = 12$ money for selling it.
- The second animal to be sold is animal $2$. Animal $a_2 = 4$ was sold before, so you receive $c_2 = 4$ money for selling it.
- The third animal to be sold is animal $5$. Animal $a_5 = 3$ was not sold before, so you receive $2 \cdot c_5 = 14$ money for selling it.
- The fourth animal to be sold is animal $1$. Animal $a_1 = 3$ was not sold before, so you receive $2 \cdot c_1 = 6$ money for selling it.
- The fifth animal to be sold is animal $3$. Animal $a_3 = 4$ was sold before, so you receive $c_3 = 5$ money for selling it.
Your total profit, with this choice of permutation, is $12 + 4 + 14 + 6 + 5 = 41$. Note that $41$ is not the maximum possible profit in this example.
$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but $4$ is present in the array).
Input
The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
Then follow the descriptions of the test cases.
The first line of each test case description contains an integer $n$ ($2 \le n \le 10^5$) — the number of animals.
The second line of the test case description contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \neq i$) — $a_i$ means the index of the animal that animal $i$ is afraid of.
The third line of the test case description contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — the costs of the animals.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
Output
Output $t$ lines, each containing the answer to the corresponding test case. The answer should be $n$ integers — the permutation $p_1, p_2, \ldots, p_n$, indicating in which order to sell the animals in order to maximize the profit. If there are multiple possible answers, you can output any of them.
Example
input
8 3 2 3 2 6 6 1 8 2 1 4 3 6 5 8 7 1 2 1 2 2 1 2 1 5 2 1 1 1 1 9 8 1 1 1 2 2 1 1000000000 999999999 7 2 3 2 6 4 4 3 1 2 3 4 5 6 7 5 3 4 4 1 3 3 4 5 6 7 3 2 1 1 1 2 2 4 2 1 4 1 1 1 1 1
output
1 2 3 2 4 5 1 6 3 7 8 3 4 5 1 2 1 2 7 5 1 3 2 6 4 5 3 2 4 1 3 2 1 3 4 1 2
解题思路
比赛最后几分钟做了出来,主要卡在了处理挂在环上的链,代码写得又长又臭。
如果从$i$到$a_i$连一条边$i \to a_i$,那么可以发现得到的图是一个基环树,这是因为每个节点都恰好有一个出度。分别考虑基环树中的环以及挂在环上的树。对于挂在环上的树,也就是不在环中的点,我们总是可以通过拓扑排序找出来,那么剩余的点自然就是环上的点了,这样就可以把环以及挂在环上的树分离开来。
对于某个节点$u$,如果存在害怕$u$的动物$v$,即$u$的入度不为$0$,那么很明显先卖$v$再卖$u$所得到的收益不会比先卖$u$再卖$v$要差。因此继续顺着找到害怕$v$的动物,以此类推直到找到某个点$x$,不存在害怕$x$的动物,即$x$的入度为$0$,那么就先售卖$x$,这样做肯定是最优的。
为此先对不在环中的点进行售卖,可以发现每个点都能获得两倍的收益。只需按照拓扑的顺序进行售卖即可,这样就可以保证每次卖掉的点的入度均为$0$。然后就是环上的点,可以发现无论按什么顺序卖掉,都至少有一个点不能获得两倍收益(因为必然存在只剩一个点的情况)。为了能得到最大收益,假设环中$c_x$最小,那么我们按照$a_x \to a_{a_x} \to \cdots \to x$的顺序进行售卖,那么除了$x$外,其余的点都能获得两倍收益。
要注意得到的图不一定是连通的,因此要分别处理每个基环树。
AC代码如下,时间复杂度为$O(n)$:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 1e5 + 10; 7 8 int a[N], c[N]; 9 int deg[N]; 10 bool vis[N]; 11 int q[N], hh, tt; 12 13 void solve() { 14 int n; 15 scanf("%d", &n); 16 memset(deg, 0, n + 10 << 2); 17 memset(vis, 0, n + 10); 18 for (int i = 1; i <= n; i++) { 19 scanf("%d", a + i); 20 deg[a[i]]++; 21 } 22 for (int i = 1; i <= n; i++) { 23 scanf("%d", c + i); 24 } 25 hh = 0, tt = -1; 26 for (int i = 1; i <= n; i++) { 27 if (!deg[i]) q[++tt] = i; 28 } 29 while (hh <= tt) { // 先把不在环上的点找出来 30 int t = q[hh++]; 31 vis[t] = true; // 不在环上的点被标记 32 printf("%d ", t); // t的入度为0,因此卖掉 33 if (--deg[a[t]] == 0) q[++tt] = a[t]; 34 } 35 for (int i = 1; i <= n; i++) { 36 if (vis[i]) continue; // 没有被标记的点一定是环上的点 37 int t = i; 38 vector<int> p; 39 while (!vis[t]) { // 把环上的点都找出来 40 vis[t] = true; 41 p.push_back(t); 42 t = a[t]; 43 } 44 int k = 0; // 找到收益最小的点 45 for (int i = 0; i < p.size(); i++) { 46 if (c[p[i]] < c[p[k]]) k = i; 47 } 48 for (int i = 0; i < p.size(); i++) { // 收益最小的点最后卖掉 49 if (++k == p.size()) k = 0; 50 printf("%d ", p[k]); 51 } 52 } 53 printf("\n"); 54 } 55 56 int main() { 57 int t; 58 scanf("%d", &t); 59 while (t--) { 60 solve(); 61 } 62 63 return 0; 64 }
参考资料
Codeforces Round 895 (Div. 3) Editorial:https://codeforces.com/blog/entry/120165