Make Bipartite

题目描述

给定一个具有 $N+1$ 个顶点的无向图。
顶点被称为顶点 $0$、顶点 $1$、$\ldots$、顶点 $N$。 对于每个 $i=1,2,\ldots,N$，图中有一条权重为 $A_i$ 的无向边连接顶点 $0$ 和顶点 $i$。 另外，对于每个 $i=1,2,\ldots,N$，图中有一条权重为 $B_i$ 的无向边连接顶点 $i$ 和顶点 $i+1$。（这里，顶点 $N+1$ 代表顶点 $1$.） 除了以上这 $2N$ 条边外，图没有其他边。 我们删除图中的若干条边，使得图成为二分图。
需要删除的边的权重总和最小是多少？

输入格式

从标准输入按以下格式给出输入： $N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$

输出格式

输出答案。

5
31 4 159 2 65
5 5 5 5 10

16

4
100 100 100 1000000000
1 2 3 4

10

提示

$3 \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq 10^9$ $1 \leq B_i \leq 10^9$ 输入中的所有值均为整数。
删除连接顶点 $0,2$ 的边（权重：$4$）、连接顶点 $0,4$ 的边（权重：$2$）以及连接顶点 $1,5$ 的边（权重：$10$）可以使图成为二分图。

标签: AtCoder|abc229F

来源

AtCoder|abc229F