A5950 | 「WC2021」括号路径
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
给定一张 $n$ 个点 $2 m$ 条边的有向图，图中的每条边上都有一个标记，代表一个左括号或者右括号。共有 $k$ 种不同的括号类型，即图中可能有 $2 k$ 种不同的标记。点、边、括号种类均从 $1$ 开始编号。
图中的每条边都会和另一条边成对出现。更具体地，若图中存在一条标有第 $w$ 种括号的左括号的边 $(u, v)$，则图中一定存在一条标有第 $w$ 种括号的右括号的边 $(v, u)$。同样地，图中每条标有右括号的边将对应着一条反方向的标有同类型左括号的边。
现在请你求出，图中共有多少个点对 $(x, y)$（$1 \le x < y \le n$）满足：图中存在一条从 $x$ 出发到达 $y$ 的路径，且按经过顺序将路径各条边上的标记拼接得到的字符串是一个合法的括号序列。
图中的每条边都会和另一条边成对出现。更具体地，若图中存在一条标有第 $w$ 种括号的左括号的边 $(u, v)$，则图中一定存在一条标有第 $w$ 种括号的右括号的边 $(v, u)$。同样地，图中每条标有右括号的边将对应着一条反方向的标有同类型左括号的边。
现在请你求出，图中共有多少个点对 $(x, y)$（$1 \le x < y \le n$）满足：图中存在一条从 $x$ 出发到达 $y$ 的路径，且按经过顺序将路径各条边上的标记拼接得到的字符串是一个合法的括号序列。
输入格式
第一行三个整数 $n, m, k$，分别表示图中的点数，边对数和括号类型数。
接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条从 $u$ 到 $v$ 的有向边，其标记为第 $w$ 种括号的左括号；以及一条从 $v$ 到 $u$ 的有向边，其标记为第 $w$ 种括号的右括号。
输入给出的图中，任意两个不同的顶点间可以有多条有向边相连，但图中不存在连向自身的有向边，即 $u \ne v$。
接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条从 $u$ 到 $v$ 的有向边，其标记为第 $w$ 种括号的左括号；以及一条从 $v$ 到 $u$ 的有向边，其标记为第 $w$ 种括号的右括号。
输入给出的图中，任意两个不同的顶点间可以有多条有向边相连，但图中不存在连向自身的有向边，即 $u \ne v$。
输出格式
输出仅一行一个整数，表示满足条件的点对数量。
输入输出样例
输入 #1
4 5 1 4 3 1 4 1 1 4 2 1 1 3 1 2 1 1
输出 #1
3
输入 #2
6 8 2 6 1 2 3 5 1 1 2 2 5 1 2 3 6 2 4 3 1 6 2 2 3 2 1
输出 #2
10
对于所有测试点：$1 \le n \le 3 \times {10}^5$，$1 \le m \le 6 \times {10}^5$，$1 \le k, u, v \le n$，$1 \le w \le k$。
每个测试点的具体限制见下表：
| 测试点编号 | $n =$ | $m \le$ | $k \le$ | 特殊限制 |
|:-:|:-:|:-:|:-:|:-:|
| $1 \sim 4$ | $4$ | $5$ | $2$ | 无 |
| $5 \sim 8$ | $8$ | $10$ | $2$ | 无 |
| $9 \sim 12$ | $3000$ | $6000$ | $1$ | 无 |
| $13 \sim 16$ | $3000$ | $n - 1$ | $n$ | 不存在仅由带左括号标记的边构成的环 |
| $17 \sim 20$ | $3 \times {10}^5$ | $n - 1$ | $n$ | 不存在仅由带左括号标记的边构成的环 |
| $21 \sim 25$ | $3 \times {10}^5$ | $6 \times {10}^5$ | $n$ | 无 |
每个测试点的具体限制见下表：
| 测试点编号 | $n =$ | $m \le$ | $k \le$ | 特殊限制 |
|:-:|:-:|:-:|:-:|:-:|
| $1 \sim 4$ | $4$ | $5$ | $2$ | 无 |
| $5 \sim 8$ | $8$ | $10$ | $2$ | 无 |
| $9 \sim 12$ | $3000$ | $6000$ | $1$ | 无 |
| $13 \sim 16$ | $3000$ | $n - 1$ | $n$ | 不存在仅由带左括号标记的边构成的环 |
| $17 \sim 20$ | $3 \times {10}^5$ | $n - 1$ | $n$ | 不存在仅由带左括号标记的边构成的环 |
| $21 \sim 25$ | $3 \times {10}^5$ | $6 \times {10}^5$ | $n$ | 无 |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？