#P3466. 动态仙人掌 III
动态仙人掌 III
动态仙人掌 III
题目描述
VFleaKing 去森林看见了会动的树,在沙漠看见了会动的仙人掌。pyx1997 说他会维护它们的形态,VFleaKing 想请你也试一试。
如果一个无向连通图的每条边至多属于一个简单环,就称它为仙人掌。如果无向图的每个连通分量都是仙人掌,并且图中没有自环,就称它为沙漠。允许两点之间有平行边,两条平行边可以组成一个环。
给定 个编号为 到 的节点,初始时没有边。依次处理以下操作。
link v u wA wB尝试在 之间加入一条权值 为 、权值 为 的边。如果加入后仍是沙漠,则保留新边并输出ok,否则撤销新增边并输出failed。cut v u wA wB删除 之间满足给定权值的一条边。若有多条符合的边,任选一条删除。删除成功输出ok,否则不做修改并输出failed。distance? v u按权值 求最短路,输出两个整数 。 是最短路长度, 是该最短路上的最小权值 。若有多条按 计算的最短路,。若两点不连通,输出-1 -1。若 ,输出0 2147483647。add v u d将 到 的唯一一条按 计算的最短路上的每条边的权值 增加 ,权值 不变。要求 。若最短路存在且唯一,执行操作并输出ok,否则不做修改并输出failed。
输入格式
第一行包含两个正整数 ,分别表示节点数和操作数。
接下来 行,每行给出一个操作。节点编号 都在 到 之间, 为正整数。
输出格式
对每次操作按照上述规则输出一行。
样例 #1
6 56
link 1 2 1 3
link 1 2 2 5
distance? 1 2
cut 1 2 1 3
link 1 2 2 5
distance? 1 2
cut 1 2 2 5
link 1 2 2 4
add 1 2 1
cut 1 2 2 4
cut 1 2 2 5
link 3 3 2 2
cut 4 4 2 2
link 1 2 2 4
link 1 3 3 5
link 2 3 4 3
distance? 1 2
distance? 1 3
distance? 2 4
add 1 2 3
link 2 4 3 2
link 3 5 3 4
link 4 5 1 5
distance? 4 5
cut 1 2 2 7
link 4 5 5 4
distance? 1 5
cut 2 3 4 3
link 2 5 5 3
link 1 5 2 4
distance? 1 2
add 3 4 3
cut 4 5 5 7
distance? 1 2
cut 3 5 3 7
distance? 1 2
cut 2 5 5 4
cut 2 5 5 3
distance? 1 2
add 1 2 3
link 3 5 6 7
distance? 1 3
add 3 5 1
distance? 5 3
distance? 4 3
link 4 6 3 1
link 2 6 7 2
distance? 2 6
link 5 6 2 4
distance? 1 6
distance? 2 3
cut 2 4 3 2
link 2 5 4 3
distance? 4 1
cut 4 6 3 1
distance? 4 1
ok
ok
1 3
ok
ok
2 -1
ok
ok
failed
ok
ok
failed
failed
ok
ok
ok
2 4
3 5
-1 -1
ok
ok
ok
failed
10 2
ok
ok
6 4
ok
ok
ok
7 3
ok
ok
7 3
ok
7 3
failed
ok
-1 -1
failed
ok
3 5
ok
5 5
-1 -1
ok
ok
6 1
ok
4 4
13 1
ok
ok
7 1
ok
-1 -1
数据范围
,。有关边权的中间计算保证不超出有符号 位整数范围。
题目来源为 VFleaKing。