| 题目名称 | 2987. 简单题subgraph |
|---|---|
| 输入输出 | subgraph.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 梦那边的美好ET
于2018-10-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：35， 通过率：20% | ||||
 胡嘉兴 |
100 | 1.404 s | 19.70 MiB | C++ |
|
胡嘉兴 |
100 | 1.552 s | 19.66 MiB | C++ |
 Akoasm |
100 | 1.937 s | 45.67 MiB | C++ |
 梦那边的美好ET |
100 | 2.746 s | 19.70 MiB | C++ |
|
胡嘉兴 |
100 | 2.755 s | 19.66 MiB | C++ |
|
... |
100 | 2.778 s | 19.70 MiB | C++ |
|
胡嘉兴 |
100 | 2.815 s | 19.70 MiB | C++ |
|
Akoasm |
90 | 6.638 s | 32.32 MiB | C++ |
|
胡嘉兴 |
80 | 2.652 s | 22.36 MiB | C++ |
|
胡嘉兴 |
80 | 2.685 s | 22.36 MiB | C++ |
| 关于 简单题subgraph 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
擅自把时间改到3s，我写了O（3^n+m*2^n）的算法只能跑到2.1s左右，如果有更优的方法请私信我
胡嘉兴
2018-10-09 21:29
1楼
| ||||
【题目描述】
大滑稽很喜欢有向图，有一天他找到了一张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。