102295: [AtCoder]ABC229 F - Make Bipartite
Description
Score : $500$ points
Problem Statement
Given is an undirected graph with $N+1$ vertices.
The vertices are called Vertex $0$, Vertex $1$, $\ldots$, Vertex $N$.
For each $i=1,2,\ldots,N$, the graph has an undirected edge with a weight of $A_i$ connecting Vertex $0$ and Vertex $i$.
Additionally, for each $i=1,2,\ldots,N$, the graph has an undirected edge with a weight of $B_i$ connecting Vertex $i$ and Vertex $i+1$. (Here, Vertex $N+1$ stands for Vertex $1$.)
The graph has no edge other than these $2N$ edges above.
Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?
Constraints
- $3 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq B_i \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$
Output
Print the answer.
Sample Input 1
5 31 4 159 2 65 5 5 5 5 10
Sample Output 1
16
Deleting the edge connecting Vertices $0,2$ (weight: $4$), the edge connecting Vertices $0,4$ (weight: $2$), and the edge connecting Vertices $1,5$ (weight: $10$) makes the graph bipartite.
Sample Input 2
4 100 100 100 1000000000 1 2 3 4
Sample Output 2
10
Input
题意翻译
### 题目描述 给你一张由 $N+1$ 个点组成的无向图，分别命名为 $0,1,...,N$ 这张图只有 $2N$ 条边，用 $A$ 和 $B$ 两个数组表示： + $A_i$ 表示连接 $0$ 和 $i$ 两点的无向边的权值 + $B_i$ 表示连接 $i$ 和 $i+1$ 两点的无向边的权值, 这里，点 $N$ 与 点 $1$ 连接 现在要删除若干条边， 使得这个图变成一张二分图，求删除边的最小权值和 ### 输入格式 第一行输入$N$，第二行输入 $A$ 数组，第三行输入 $B$ 数组 ### 输出格式 一行，即答案 ### 数据范围 - $ 3\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ B_i\ \leq\ 10^9 $ - 输入的所有数据都在整型范围内 ### 样例解释  删除 $(0,2),(0,4),(0,5)$ 三条边Output
得分：500分
问题描述
给定一个有$N+1$个顶点的无向图。
顶点分别被称为顶点$0$、顶点$1$、$\ldots$、顶点$N$。
对于每个$i=1,2,\ldots,N$，图中有一条从顶点$0$到顶点$i$的权重为$A_i$的无向边。
此外，对于每个$i=1,2,\ldots,N$，图中有一条从顶点$i$到顶点$i+1$的权重为$B_i$的无向边。（这里，顶点$N+1$表示顶点$1$。）
除了上述$2N$条边外，图中没有其他边。
从这个图中删除一些边，使得图变为二分图。要删除的边的最小总权重是多少？
约束
- $3 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq B_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入给出：
$N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$
输出
打印答案。
样例输入1
5 31 4 159 2 65 5 5 5 5 10
样例输出1
16
删除连接顶点$0,2$（权重：$4$）的边，连接顶点$0,4$（权重：$2$）的边，以及连接顶点$1,5$（权重：$10$）的边，可以使图变为二分图。
样例输入2
4 100 100 100 1000000000 1 2 3 4
样例输出2
10