题目详情题解（0）讨论（0）提交记录（0）

AT_abc229_f.[ABC229F] Make Bipartite

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一张由 N+1N+1 个点组成的无向图，分别命名为 0,1,...,N0,1,...,N

这张图只有 2N2N 条边，用 AA 和 BB 两个数组表示：

  • AiA_i 表示连接 00 和 ii 两点的无向边的权值
  • BiB_i 表示连接 ii 和 i+1i+1 两点的无向边的权值, 这里，点 NN 与 点 11 连接

现在要删除若干条边， 使得这个图变成一张二分图，求删除边的最小权值和

输入格式

第一行输入NN，第二行输入 AA 数组，第三行输入 BB 数组

输出格式

一行，即答案

输入输出样例

  • 输入#1

    5
31 4 159 2 65
5 5 5 5 10

    输出#1

    16

  • 输入#2

    4
100 100 100 1000000000
1 2 3 4

    输出#2

    10

说明/提示

  • $ 3\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
  • $ 1\ \leq\ A_i\ \leq\ 10^9 $
  • $ 1\ \leq\ B_i\ \leq\ 10^9 $
  • 输入的所有数据都在整型范围内

样例解释

graph
删除 (0,2),(0,4),(0,5)(0,2),(0,4),(0,5) 三条边

输入解题思路，AI测评打分。不知道怎么写?

首页