← 返回题目列表

AtCoder · agc028_c

C. 最小成本周期

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

我们有一个有向加权图 N 顶点。 每个顶点上面写有两个整数,Vertex上写的整数 i 是 A_i 和 B_i.

在此图中,有一条来自 Vertex 的边 x 到顶点 y 对于所有对 1 \leq x,y \leq N,其权重为 {\rm min}(A_x,B_y).

我们将考虑该图中的有向循环,该循环仅访问每个顶点一次。 求这样一个循环中边的最小总权重。

约束

  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
:
A_N B_N

输出

打印这样一个循环中边缘的最小总重量。


示例输入 1

3
1 5
4 2
6 3

示例输出 1

7

考虑循环 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.


示例输入 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