[AGC028C] Min Cost Cycle
题意翻译
- 给定一个 $n$ 边的有向完全图,每个点有两个点权 $a$ 和 $b$,一条边 $(u,v)$ 的边权值的计算方法为 $\min(a_u,b_v)$。
- 求边权和最小的哈密顿回路的边权和。
- 对于 $100\%$ 的数据,$2 \le n \le 10^5$,$1 \le a,b \le 10^9$。
- Translated by 一只书虫仔。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc028/tasks/agc028_c
$ N $ 頂点の重み付き有向グラフがあります。 各頂点には $ 2 $ つの整数が書かれており、頂点 $ i $ には $ A_i $ と $ B_i $ が書かれています。
このグラフには、任意の $ 1\ \leq\ x,y\ \leq\ N $ について 頂点 $ x $ から頂点 $ y $ へ向かう辺があり、その重みは $ {\rm\ min}(A_x,B_y) $ です。
このグラフの有向サイクルであって、すべての頂点をちょうど $ 1 $ 度ずつ通るものを考えます。 そのようなサイクルの辺の重みの総和の最小値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_N $ $ B_N $
输出格式
すべての頂点をちょうど $ 1 $ 度ずつ通るサイクルの辺の重みの総和の最小値を出力せよ。
输入输出样例
输入样例 #1
3
1 5
4 2
6 3
输出样例 #1
7
输入样例 #2
4
1 5
2 6
3 7
4 8
输出样例 #2
10
输入样例 #3
6
19 92
64 64
78 48
57 33
73 6
95 73
输出样例 #3
227
说明
### 制約
- $ 2\ \leq\ N\ \leq\ 10^5 $
- $ 1\ \leq\ A_i\ \leq\ 10^9 $
- $ 1\ \leq\ B_i\ \leq\ 10^9 $
- 入力はすべて整数である。
### Sample Explanation 1
頂点 $ 1→3→2→1 $ というサイクルを考えると、その辺の重みは、$ {\rm\ min}(A_1,B_3)=1 $, $ {\rm\ min}(A_3,B_2)=2 $, $ {\rm\ min}(A_2,B_1)=4 $ となり、 その総和は $ 7 $ になります。 辺の重みの総和を $ 7 $ より小さくすることは出来ないので、答えは $ 7 $ になります。