比赛场次 275
比赛名称 Asm_Def战记之透明计算网络
比赛状态 已结束比赛成绩
开始时间 2015-11-01 08:10:00
结束时间 2015-11-01 12:00:00
开放分组 全部用户
注释介绍
题目名称 Asm_Def三角形
输入输出 tria.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatardebug AAAAAAAWWW 0.015 s 0.29 MiB 70
Gravatarmikumikumi WWWAAAAWWW 0.002 s 0.29 MiB 40
GravatarSatoshi WWWAAAAWWW 0.002 s 0.31 MiB 40
Gravatar前鬼后鬼的守护 AAAWWWWWWA 0.029 s 0.29 MiB 40
Gravatarlxtgogogo TTTAAAAWWW 3.044 s 1.66 MiB 40
GravatarTabing010102 WWAWWWWWWW 0.000 s 0.31 MiB 10
GravatarTychus WWWWWWWWWA 0.002 s 0.31 MiB 10
GravatarCollor WWWWWWWWWA 0.002 s 95.68 MiB 10
GravatarJobs.T WWWWWWWWWA 0.003 s 0.31 MiB 10
Gravatarlzh WWWWWWWWWA 0.004 s 0.31 MiB 10
Gravatartyphon WWWWWEEWWA 0.008 s 0.17 MiB 10
Gravatarslyterlins WWWWWWWWWA 0.008 s 0.70 MiB 10
Gravatarfyb WWAWWWWWWW 0.044 s 0.29 MiB 10
GravatarWAHT WWWWWWWWWA 0.055 s 0.32 MiB 10
GravatarVG|Kn. WWWWWWWWWA 0.158 s 1.46 MiB 10
GravatarTZJerry TTTWWWWWWA 3.002 s 0.36 MiB 10
Gravatarfengchenxue C 0.000 s 0.00 MiB 0
Gravatarpppoooiiizzy C 0.000 s 0.00 MiB 0
Gravatarmomo123 C 0.000 s 0.00 MiB 0
GravatarTen.X WWWWWWWWWW 0.000 s 0.15 MiB 0
GravatarWINAPI RRRRRRRRRR 0.006 s 1.45 MiB 0
Gravatarasddddd WWWWWWWWWW 0.013 s 1.15 MiB 0
GravatarFmuckss WWWWWWWWWW 0.033 s 0.31 MiB 0
GravatarTear smile WWWWWWWWWW 0.058 s 2.22 MiB 0
Gravatarsro dydxh orz WWWWWWWEEE 0.232 s 191.05 MiB 0
GravatarNVIDIA WWWWWWWTTT 3.031 s 2.41 MiB 0
Gravatarcoo EEEEEEEEEE 4.319 s 1.31 MiB 0
Gravatar321Rain WWWWWTTTTT 5.006 s 1.55 MiB 0

Asm_Def三角形

★★☆   输入文件:tria.in   输出文件:tria.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


Asm.Def已经突破了圣迭戈的基础防御设施,来到了透明计算网络所在的机房,发现事情并非想象的那样简单。

由于透明计算网络的特性,可以实现文件多节点储存、计算资源的实时调度。摧毁它并非易事。透明计算网络可以抽象成一张图,它的每个节点都互相连接。透明计算网络采用的调度策略有缺陷,如果使整张网络中任意(即所有)三个点组成的三角形,之间的链接断开一条或者三条全部断开,可使得整个服务离线。

现在有些链接被加固,即不可能被断开。有些链接已经被断开。现在让你选择断开一些链接使得整个服务离线,有多少种方案呢?方案数对998244353取模。认为两个方案不同仅当存在一条边在这两个方案中一个被断开,另一个没有断开。


【输入格式】


第一行两个整数n和m,表示有n个节点,和已经有m个链接被断开或者加固。

接下来m行每行三个整数op u v,op为1是表示u和v的链接被加固,op为0是表示u和v的链接被断开。


【输出格式】

一行一个整数,表示有多少中方案。方案数对998244353取模。

【样例输入1】

3 0

【样例输出1】

4

【样例输入1说明】


样例一解释

可以断开1-2,2-3,1-3的链接,或1-2的链接,或2-3的链接,或1-3的链接。共4种方案


【样例输入2】

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

【样例输出2】

1

【样例输入2说明】


只能断开1-3,使得三角形(1,2,3)全部被断开,三角形(1,4,3)只被断开一条边


【样例输入3】

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

【样例输出3】

0

【数据规模与约定】

30%的数据,1 <= n <= 7,m <= 21

另外40%的数据,1 <= n <= 100000,m = 0

另外30%的数据,1 <= n <= 100000,m <= 100000

【来源】

Asm_Def战记之透明计算网络