#P7018. [2017年成都七中集训]跨越国度

    ID: 6849 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>计算几何树算法LCA图论数据结构CF2800树的重心线段树分治

[2017年成都七中集训]跨越国度

跨越国度(country)

题目描述

X星球有 pp 个国家,每个国家的领土是平面上的一个简单多边形,各国公共面积为0,每个国家至少与一个国家相邻。全部领土的并集也是简单多边形,并集以外的地区不属于任何国家。输入以全部顶点和线段描述这些领土的分布。

共有 cc 个民族,每个国家由其中一个民族统治。相邻国家的公共边是国界,其权值 ww 表示跨越费用;w=−1w=-1 表示不能跨越该边。保证任意两个国家之间存在唯一一条可以跨越国界的路径。路径费用为经过的国界权值之和。

两个统治民族相同的国家可以进行友好往来,费用为它们之间上述唯一路径的费用。

现在需要支持将某个国家的统治民族修改为给定民族,并求全部同民族国家对中最小的往来费用。如果不存在两个统治民族相同的国家,输出 −1-1。

输入按顺时针给出某个国家的两条相邻边的编号,以该国家的一个角指代这个国家。同一国家可以有不同的指代方式。

输入格式

第一行五个整数 n,m,p,c,tn,m,p,c,t,依次表示顶点数、线段数、国家数、民族数和修改次数。其中 n,m,p,cn,m,p,c 为正整数,tt 可为0。

接下来 nn 行,第 ii 行两个正整数,表示编号为 ii 的顶点坐标。

接下来 mm 行,第 ii 行三个整数 u,v,wu,v,w,表示连接顶点 u,vu,v、权值为 ww 的第 ii 条边。所有边仅在顶点处相交。

接下来 pp 行,描述每个国家的初始统治民族。每行三个正整数,前两个数按顺时针给出该国家两条相邻边的编号,第三个数为统治民族编号。

最后 tt 行描述修改操作,格式相同:前两个数指代国家,第三个数为修改后的统治民族。

边的编号为 1,…,m1,\ldots,m,民族编号为 1,…,c1,\ldots,c。

输出格式

输出 t+1t+1 行,依次表示初始状态及每次修改后的最小往来费用。

样例输入1

6 8 3 3 2
6 7
4 4
8 4
2 1
6 1
10 1
1 2 -1
1 3 -1
2 4 -1
2 5 5
3 5 8
3 6 -1
4 5 -1
5 6 -1
2 1 1
4 3 2
6 5 3
8 6 1
3 7 1

样例输出1

-1
8
5

样例解释

三国的国界及可跨越费用

初始有A、B、C三个国家,统治民族各不相同。只有A与B、A与C之间的国界可以跨越,费用分别为5、8。

  • 初始没有同民族的两个国家,答案为 −1-1。
  • 第一次修改后,C与A的统治民族相同,答案为8。
  • 第二次修改后,三个国家统治民族相同,答案为5。

数据范围

测试点 民族数 cc 上界 国家数 pp 上界 修改次数 tt 限制 附加条件
1—2 1010 500500 t=0t=0 各国领土均为边平行于坐标轴的矩形
3—4 100100 无
5 1010 20002000 各国领土均为边平行于坐标轴的矩形
6 20002000 无
7 1010 50005000 各国领土均为边平行于坐标轴的矩形
8 50005000 无
9 1010 70007000 各国领土均为边平行于坐标轴的矩形
10 70007000 无
11 1010 90009000 各国领土均为边平行于坐标轴的矩形
12 90009000 无
13—14 1010 1000010000 t≤10000t\le10000 各国领土均为边平行于坐标轴的矩形
15—16 1000010000 无
17—18 1010 1200012000 t≤2000t\le2000 各国领土均为边平行于坐标轴的矩形
19—20 1200012000 无

全部数据中,顶点数和边数均不超过国家数的10倍,坐标不超过10000。国界费用为 −1-1 或不超过10000的正整数。