307750: CF1408E. Avoid Rainbow Cycles
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Avoid Rainbow Cycles
题意翻译
有 $m$ 个集合 $A_1,A_2,\dots,A_m$，它们包含的元素为 $[1,n]$ 中的整数。 在第 $i$ 个集合中删掉元素 $j$ 的代价为 $a_i+b_j$ 。你可以删掉任何集合中的任何元素（也可以不删除）。 现在有一个 $n$ 个节点的无向图，如果删除操作结束以后元素 $x,y(x<y)$ 在集合 $i$ 中同时存在，则在 $x,y$ 间连一条颜色为 $i$ 的边（可以有颜色不同的重边）。 问最小的代价，使得删除完元素后形成的图不存在一个每条边颜色都不同的环（环长可以为 $2$）。题目描述
You are given $ m $ sets of integers $ A_1, A_2, \ldots, A_m $ ; elements of these sets are integers between $ 1 $ and $ n $ , inclusive. There are two arrays of positive integers $ a_1, a_2, \ldots, a_m $ and $ b_1, b_2, \ldots, b_n $ . In one operation you can delete an element $ j $ from the set $ A_i $ and pay $ a_i + b_j $ coins for that. You can make several (maybe none) operations (some sets can become empty). After that, you will make an edge-colored undirected graph consisting of $ n $ vertices. For each set $ A_i $ you will add an edge $ (x, y) $ with color $ i $ for all $ x, y \in A_i $ and $ x < y $ . Some pairs of vertices can be connected with more than one edge, but such edges have different colors. You call a cycle $ i_1 \to e_1 \to i_2 \to e_2 \to \ldots \to i_k \to e_k \to i_1 $ ( $ e_j $ is some edge connecting vertices $ i_j $ and $ i_{j+1} $ in this graph) rainbow if all edges on it have different colors. Find the minimum number of coins you should pay to get a graph without rainbow cycles.输入输出格式
输入格式
The first line contains two integers $ m $ and $ n $ ( $ 1 \leq m, n \leq 10^5 $ ), the number of sets and the number of vertices in the graph. The second line contains $ m $ integers $ a_1, a_2, \ldots, a_m $ ( $ 1 \leq a_i \leq 10^9 $ ). The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \leq b_i \leq 10^9 $ ). In the each of the next of $ m $ lines there are descriptions of sets. In the $ i $ -th line the first integer $ s_i $ ( $ 1 \leq s_i \leq n $ ) is equal to the size of $ A_i $ . Then $ s_i $ integers follow: the elements of the set $ A_i $ . These integers are from $ 1 $ to $ n $ and distinct. It is guaranteed that the sum of $ s_i $ for all $ 1 \leq i \leq m $ does not exceed $ 2 \cdot 10^5 $ .
输出格式
Print one integer: the minimum number of coins you should pay for operations to avoid rainbow cycles in the obtained graph.
输入输出样例
输入样例 #1
3 2
1 2 3
4 5
2 1 2
2 1 2
2 1 2输出样例 #1
11输入样例 #2
7 8
3 6 7 9 10 7 239
8 1 9 7 10 2 6 239
3 2 1 3
2 4 1
3 1 3 7
2 4 3
5 3 4 5 6 7
2 5 7
1 8输出样例 #2
66