题目名称 2987. 简单题subgraph
输入输出 subgraph.in/out
难度等级 ★★★
时间限制 3000 ms (3 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2018-10-07
开放分组 全部用户
提交状态
分类标签
hs的简单题
通过:1, 提交:23, 通过率:4.35%
Gravatar梦那边的美好ETMN 100 4.786 s C++
Gravatarluo 100 4.791 s C++
Gravatarluo 100 4.826 s C++
Gravatarluo 100 5.174 s C++
Gravatarluo 100 5.196 s C++
Gravatarluo 80 2.509 s C++
Gravatarluo 80 2.647 s C++
Gravatarluo 80 2.652 s C++
Gravatarluo 80 2.685 s C++
Gravatarluo 80 2.906 s C++
关于 简单题subgraph 的讨论
擅自把时间改到3s,我写了O(3^n+m*2^n)的算法只能跑到2.1s左右,如果有更优的方法请私信我
Gravatarluo
2018-10-09 21:29 1楼

2987. 简单题subgraph

★★★   输入文件:subgraph.in   输出文件:subgraph.out   简单对比
时间限制:3 s   内存限制:256 MB

【题目描述】


大滑稽很喜欢有向图,有一天他找到了一张n个点m条边的有向图。

大滑稽认为一个没有环的有向图是优美的,请问这张图有多少个子图(即选定一个边集)是优美的?答案对1,000,000,007取模。


【输入格式】


第一行两个整数n和m。

接下来m行每行两个整数表示一条有向边。保证无重边无自环。


【输出格式】


一行一个整数表示答案,对1,000,000,007


【样例输入】

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

【样例输出】

25

【提示】


对于40%的数据n<=5,m<=20;

对于60%的数据n<=10;

对于80%的数据n<=15;

对于100%的数据n<=17。