#P9097. [PA2020] Elektrownie i fabryki

[PA2020] Elektrownie i fabryki

题目描述

题目译自 PA 2020 Runda 2 Elektrownie i fabryki

为了应对不断上升的失业率,Byteotia 政府决定创造新的就业机会。为此将建设现代化的工厂,还要建设为工厂供电的新发电厂。

一条很长的高速公路穿过 Byteotia,沿途有 nn 个城市。为了简单起见,我们从 11nn 对城市进行编号。每两个相邻城市之间都相距一公里。

目前已经决定一些城市建设工厂,另一些城市建设发电厂。对于第 ii 个城市有一个值 aia_i。如果它是正数,则在第 ii 个城市将建造一个发电容量为 aia_i 兆瓦的发电厂,如果它是负数,则在该城市将建造一个消耗电能 aia_i 兆瓦的工厂。如果 ai=0a_i=0,则说明该城市没有建设计划。

你的任务是设计一个电网,将电力从发电站输送到工厂。对于每一对相邻的城镇,你必须决定是否在它们之间建立一条输电线。如果这个城市被输电线直接或间接连接到某个有发电站的城市,电力就可以从发电站流向这个城市的工厂。如果每个工厂的电力需求都得到满足,那么电网的设计就是正确的。电网的成本与电网输电线的总长度(以公里计)成正比。

写一个程序计算设计一个正确的电网最小成本是多少。

输入格式

第一行一个整数 nn,表示 Byteotia 的城市个数。

第二行 nn 个整数 a1,a2,,ana_1,a_2,\cdots,a_n,表示每个城市电力的生产和消耗。

输出格式

输出设计一个正确的电网的最小成本。如果不存在一个正确的电网,输出 1-1

17
2 -5 0 2 0 0 0 4 0 0 -1 4 0 0 0 0 -3
12

提示

样例 1 解释

下面是一个包含 n=17n=17 个城市的样例,其中将建造三个工厂(白圈)和四个发电厂(黑圈)。1212 公里的正确电网用灰色部分标记。


数据范围

本题采用捆绑测试

对于一些子任务,满足 n5×103n\le 5\times 10^3

对于 100%100\% 的数据,保证 1n5×1051\le n\le 5\times 10^5109ai109-10^9\le a_i\le 10^9