#2114. 仙人掌染色

    ID: 2114 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest1899来源:qoj.ac数据:公开样例动态规划树形DP

仙人掌染色

仙人掌染色

题目描述

IOI2025 中国国家队选拔 第二试仙人掌染色(color) 仙人掌染色(color) 【题目描述】 定义一个.无.自.环、.无.重.边.的.无.向.连.通.图是.仙.人.掌.图,当且仅当其.任.意.一.条.边.至.多.属 .于.一.个.简.单.环,其中简单环指不经过重复结点的环。 给定平面上的n 个点,第i 个点的坐标为(xi, yi)。给定m 条边,第i 条边连接结 点ui, vi。.保.证.由.这n .个.点.与m .条.边.构.成.的.无.向.图.为.仙.人.掌.图。 初始时,所有的m 条边都是白色的。你可以选择若干条边,并将其染成黑色,其中 将第i 条边染成黑色的代价为wi。 对于每对有公共结点的异色边,设从白色边开始沿公共结点.逆.时.针转x 条边可以到 达黑色边,那么可以获得p × x 的能量。特别地,对于两条共线且方向相同的边(即另 一结点关于公共结点的极角相同的边),规定先到达编号较小的边,也即,编号较小的 边的极角更小。 求染色后可以获得的能量总和减去染色代价总和的最大值。 【输入格式】 从文件color.in 中读入数据。 输入的第一行三个正整数n, m, p,分别表示结点个数、边数、以及获得能量的系数。 接下来m 行,第i 行三个整数ui, vi, wi,表示第i 条边的结点与代价。 接下来n 行,第i 行两个整数xi, yi,表示第i 个点的坐标。 【输出格式】 输出到文件color.out 中。 输出一行一个整数,表示染色后可以获得的能量总和减去染色代价总和的最大值。 【样例1 输入】 5 4 10 1 1 4 1 2 2 3 2 3 第2 页 共11 页 IOI2025 中国国家队选拔 第二试仙人掌染色(color) 3 4 2 4 3 5 2 5 0 1 6 1 1 7 0 0 8 1 0 9 2 0 10 【样例1 输出】 38 1 【样例1 解释】 如下图所示,黑色实线表示被染成黑色的边,灰色点线表示仍为白色的边。 花费2 的代价将(3, 4) 染为黑色后,从(1, 4) 沿结点4 逆时针转1 条边可以到达 (3, 4),获得10 × 1 = 10 能量;从(2, 3) 沿结点3 逆时针转1 条边可以到达(3, 4)(注 意:根据题目描述中的规定,会先到达(3, 4) 后到达(3, 5)),获得10 × 1 = 10 能量;从 (3, 5) 沿结点3 逆时针转2 条边可以到达(3, 4),获得10 × 2 = 20 能量。因此染色后可 以获得的能量总和为10 + 10 + 20 = 40,代价总和为2,所求的最大值为40 −2 = 38。 可以证明,不存在答案更大的染色方案。 【样例2】 见选手目录下的color/color2.in 与color/color2.ans。 【子任务】 对于所有测试数据,保证 • 2 ≤n, m ≤2 × 105,1 ≤p ≤1000, • ∀1 ≤i ≤m, 1 ≤ui, vi ≤n, 0 ≤wi ≤104, 第3 页 共11 页 IOI2025 中国国家队选拔 第二试仙人掌染色(color) • ∀1 ≤i ≤n, 0 ≤xi, yi ≤107, • 给定的图是仙人掌图; • 任意两个点坐标不重合。 子任务编号 分值 特殊性质 n, m ≤ 1 7 AB 20 2 9 无 3 3 AB 4 9 8000 A 5 30 无 6 11 A 7 1 C 200000 8 12 D 9 18 无 特殊性质A:保证m = n −1,也即给定的图是一棵树。 特殊性质B:保证给定的图上任意一对没有公共结点的边在平面上不相交,也即给 定的图是平面嵌入。 特殊性质C:保证∀1 ≤i ≤m, wi = 0。 特殊性质D:保证∀1 ≤i ≤m, wi = 1,p = 1。 第4 页 共11 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 4 10
1 4 1
2 3 2
3 4 2
3 5 2
0 1
1 1
0 0
1 0
2 0
38