P2128 赤壁之战

    • 358通过
    • 903提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 搜索 数论,数学
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    赤壁之战,黄盖率舰满载薪草膏油诈降曹军。

    受庞统所授的连环计,曹军战船之间由铁索相连,没有两艘战船在同一位置,也没有铁索两两相交或穿过战船。每艘船都有其一定的战略价值。

    为了保证达到破坏效果,黄盖需要保证被点燃的曹军船只两两之间都有铁索连接。他希望找到一种方案点燃总价值尽可能大的战船。

    输入输出格式

    输入格式:

    第一行包含数字 N; M ,表示战船的数量和铁索的数量。

    接下来包含 N 行,每 i 行包含 1 个数字 Vi ,表示第 i 艘战船的战略价值。

    接下来包含 M 行,每 i 行包含 2 个数字 Si; Ti ,表示铁索连接的两艘船只。

    数据保证这是一个可行的舰队安排。

    输出格式:

    输出一个数字,表示最多摧毁总价值多少的战船。

    输入输出样例

    输入样例#1: 复制
    4 6
    100
    5000
    1000
    2000
    1 2
    1 3
    1 4
    2 3
    2 4
    3 4
    输出样例#1: 复制
    8100
    输入样例#2: 复制
    6 8
    1500
    1000
    100
    2000
    500
    300
    1 2
    1 3
    1 4
    2 4
    3 5
    4 5
    4 6
    5 6
    输出样例#2: 复制
    4500

    说明

    【数据规模】

    对于50%的数据,保证 N,M ≤ 10。

    对于100%数据,保证 N ≤ 450; M ≤ 900; Vi ≤ 6000。

    【注意】

    题目中的每句话(除了第一段)都有作用。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。