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了,可以的话,请您参考添加页面,与大家一起分享你的题解!