UOJ Logo Universal Online Judge

UOJ

#962. 【UR #30】交通管制

附件下载 统计

English Problem Statement

跳蚤国运动会在首都跳蚤利亚举行,来自全国各地的跳蚤居民蜂拥而至。为了确保运动会期间的交通秩序,跳蚤国王决定对首都的道路进行管制。

跳蚤利亚的道路系统可以看作一张由 $n$ 个路口和 $m$ 条双向道路 $(u,v)$ 组成的网络。保证 $u\ne v$,且对于每对路口之间,最多存在一条道路(即没有重边,自环)。

国王需要选择一部分道路保持开放,其余道路暂时封闭。

然而,为了保证观众能顺利抵达赛场并为心仪的战队加油,开放的道路必须满足一系列特殊限制:

对于第 $i$ 个限制,从路口 $s_i$ 到路口 $t_i$,在开放的道路中至少要存在 $c_i$($1\le c_i\le 2$)条不同的边简单路径。

  • 边简单路径的定义是:不经过重复道路的路径,且一条道路不允许从两个方向经过。
  • 不同的边简单路径的定义是:经过的路口序列不完全相同的边简单路径。
  • 特别地,路径可以只经过一个路口,在 $s_i=t_i$ 时这类路径也应被计入。

你需要帮助跳蚤国王计算出满足所有限制条件的道路开放方案数,答案对 $998244353$ 取模。

形式化题面:

给定一张 $n$ 个点 $m$ 条边的无向图 $G=(V,E)$,求有多少边集 $E'$ 满足:

  • $E' \subseteq E$
  • $(V,E')$ 满足给出的 $k$ 条限制:第 $i$ 条限制是在 $(V,E')$ 上,从 $s_i$ 到 $t_i$ 必须至少有 $c_i$ 条不同的边简单路径($1 \le c_i \le 2$)。

答案对 $998244353$ 取模。

输入格式

第一行三个整数 $n,m,k$。分别表示路口数、道路数、限制数量。

接下来 $m$ 行,每行两个整数 $u,v$,描述一条道路 $(u,v)$。保证没有重边、自环。

接下来 $k$ 行,每行三个整数 $s_i,t_i,c_i$,描述一条限制。

输出格式

一行一个整数,表示满足所有限制条件的道路开放方案数对 $998244353$ 取模的结果。

样例零

input

4 6 4
1 2
1 3
1 4
2 3
2 4
3 4
1 2 1
1 1 2
2 3 2
2 4 2

output

19

样例一~七

见下发文件。

数据范围

对于所有数据,保证 $1 \le n \le 16$,$0 \le m \le \dbinom{n}{2}$,$0 \le k \le n(n-1)$,$1 \le u \neq v \le n$,$1 \le s_i,t_i \le n$,$1 \le c_i \le 2$。

子任务编号 分值 $n\le$ 特殊性质
$1$ $10$ $7$
$2$ $10$ $16$ $c_i=1$
$3$ $30$ $10$
$4$ $10$ $12$
$5$ $10$ $14$
$6$ $15$ $15$
$7$ $15$ $16$

时间限制:$\texttt{4s}$

空间限制:$\texttt{1GB}$