← 返回题目列表

Codeforces · 1870/H

H. 标准图问题

中文机器翻译题面 查看原题

给您一个带 $$$n$$$ 个顶点和 $$$m$$$ 个边的加权有向图。图中的每个顶点可以是突出显示的,也可以是普通的。最初,所有顶点都是法线的。图的成本被定义为需要选择的边权重的最小总和,以便仅使用选定的边就可以从每个正常顶点到达至少一个突出显示的顶点。如果无法选择边,则成本为 $$$-1$$$。

您的任务是在每个 $$$q$$$ 查询之后计算图表的成本。查询可以有两种类型:

- $$$+\;v_i$$$ 使顶点 $$$v_i$$$ 突出显示;保证查询前顶点是正常的。
- $$$-\;v_i$$$ 使顶点 $$$v_i$$$ 正常;确保在查询之前该顶点被突出显示。

在每个 $$$q$$$ 查询之后输出图表的成本。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$3 \le n \le 2 \cdot 10^5, 1 \le m, q \le 2 \cdot 10^5$$$) — 图中的顶点数、边数和查询数。

接下来的 $$$m$$$ 行包含图形的边,每行一条边。第 $$$i$$$ 行包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$c_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \ne v_i, 1 \leq c_i \leq 10^6$$$) — 第 $$$i$$$ 边的端点(从$$$u_i$$$ 到 $$$v_i$$$) 及其权重 ($$$c_i$$$)。

接下来的 $$$q$$$ 行包含查询,每行一个查询。如果是第一种类型的查询,则第 $$$i$$$ 行包含 $$$+\;v_i$$$;如果是第二种类型的查询,则包含 $$$-\;v_i$$$ ($$$1 \leq v_i \leq n$$$)。

输出

输出 $$$q$$$ 数字。第 $$$i$$$ 数字是第一个 $$$i$$$ 查询后图表的成本。

示例

输入 #1

4 5 6
1 2 1
2 3 5
3 2 3
4 1 8
2 1 4
+ 1
- 1
+ 3
+ 1
+ 4
+ 2

输出 #1

15
-1
14
12
4
0

输入 #2

10 14 10
8 6 4
2 5 1
3 5 4
1 6 3
1 3 7
7 2 1
6 1 3
4 10 1
4 6 5
5 4 1
5 8 10
10 9 1
9 5 1
9 7 6
+ 7
+ 8
- 7
+ 10
+ 2
- 10
+ 5
- 2
- 5
+ 3

输出 #2

28
24
29
19
18
24
18
19
29
20

注意

在第一个测试中:

- 第一次查询后,选择编号为 $$$3, 4, 5$$$ 的边最有利可图,它们的总成本为 $$$15$$$。
- 第二次查询后,没有突出显示的顶点,这意味着没有合适的边集,图的成本为 $$$-1$$$。
- 第三次查询后,选择编号为 $$$1, 2, 5$$$ 的边最有利可图,它们的总成本为 $$$14$$$。
- 第四次查询后,选择编号为 $$$4$$$ 和 $$$5$$$ 的边最有利,它们的总成本为 $$$12$$$。
- 第五次查询后,仅选择边数 $$$5$$$ 是最有利可图的,其成本为 $$$4$$$。
- 第六次查询后,所有顶点都突出显示,无需选择任何边,图的成本为 $$$0$$$。