Skip to content

14215: 【原4215】白色相簿

题目

题目描述

author: 泰玛什 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4215

Background

小T是个二刺螈，他发现动漫里有很多令人头疼的三角关系。

Description

在一部动漫中，我们将所有角色从1到n编号。

对于任意三个角色a,b,c，小T讨厌以下两种情况：

  • a和b互相喜欢，b和c互相喜欢，而a和c互相讨厌

  • a,b,c之间均相互讨厌

小T在追一部新番。在目前的剧情中，他已经知道了角色之间的m对关系。在剩下的未知关系中，他想知道有多少种方案能使得这部动漫中没有他讨厌的三角关系。

Input Format

第一行有两个个整数\(n, m\)

接下来\(m\)行，每行三个整数\(a,b,c\)\((1 \leq a, b \leq n, a \neq b, c \in {0,1})\)。若\(c=1\)，表示\(a,b\)之间互相喜欢，否则他们之间互相讨厌。

保证任意一对关系不会被描述两次。

Output Format

一个整数，表示不被讨厌的方案数，由于数目可能很大，请输出对\(10^9+7\)取模后的结果。

Sample Input 0

3 0

Sample Output 0

4

Sample Input 1

4 4
1 2 1
2 3 1
3 4 0
4 1 0

Sample Output 1

1

Hint

在第二个例子中，唯一解是1和3互相喜欢，2和4互相讨厌。

Hint2

大家把握好愚人节的好机会。

Limit

  • 对于前10%的数据，\(m=n*(n-1)/2\)

  • 对于前30%的数据，\(n \leq 5\)

  • 对于另30%的数据，输入关系满足\(c = 1\)

  • 对于100%的数据，\(3 \leq n \leq 1e5\), \(0 \leq m \leq 1e5\)

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！