#1910. Utopiosphere
Utopiosphere
Utopiosphere
题目描述
标题: Utopiosphere - Problem - QOJ.ac
#10308. Utopiosphere
The problem was used in the following contests:
称无重边,无自环的无向图为简单无向图。
给定一个 n 个点 m 条边的简单无向图 G。若我们给 G 的每条边指定一个整数值作为边权。满足每条边的边权都在 1 到 m 之间,且每条边的边权两两不同,则称这样的指定方法为 G 的一个赋值。
两个赋值 G0,G1 称为等价的,当且仅当对于 G 的每个子图 G′,其在两种赋值下的最小生成森林形状相同(即在忽略边权的情况下是同一个子图)。
给定一个 G 的赋值 G0,求与它等价的赋值的数量,答案对 998244353 取模。
一个带正权的无向图的最小生成森林,是指连通块数与原图相同的边权和最小的子图,可以证明,如果每条边的边权两两不同,那么这样的子图是唯一的。
输入格式
从标准输入读入数据。
第一行:两个整数 n,m。
接下来 m 行:每行三个整数 x,y,z,表示 G0 中 x,y 之间有一条边权为 z 的边。
保证每条边的边权都在 1 到 m 之间,且所有边权两两不同。
输出格式
输出到标准输出。
第一行:一个整数 ans,表示答案对 998244353 取模。
样例
输入
4 6
1 2 1
1 3 2
1 4 4
2 3 3
2 4 6
3 4 5
输出
8
解释
有如下八种赋值方式(边的顺序与输入一致):
- [1,2,3,4,6,5]
- [1,2,4,3,6,5]
- [1,3,2,4,6,5]
- [2,1,3,4,6,5]
- [2,1,4,3,6,5]
- [2,3,1,4,6,5]
- [3,1,2,4,6,5]
- [3,2,1,4,6,5]
子任务
对于全部数据:1≤n,m≤2×105。
Subtask 1 (10%):n≤12, m≤6。
Subtask 2 (15%):n,m≤200。
Subtask 3 (20%):n≤2000。
Subtask 4 (2%):G 是树。
Subtask 5 (13%):G 是仙人掌。
Subtask 6 (15%):G 是杏仁。
Subtask 7 (25%):无特殊限制。
下面是对上面一些图论术语的解释。
树:没有简单环的简单无向连通图。
仙人掌:任何一条边在至多一个简单环上的简单无向连通图。
杏仁:恰好有 n−2 个点的度数为 2 的简单无向连通图。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 6
1 2 1
1 3 2
1 4 4
2 3 3
2 4 6
3 4 5
8