| 题目名称 | 2682. 膜拜 |
|---|---|
| 输入输出 | OrzOrz.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 16 |
| 题目来源 |
 TARDIS
于2017-04-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：18， 提交：61， 通过率：29.51% | ||||
 jekyll |
100 | 0.162 s | 7.94 MiB | C++ |
 RainyC |
100 | 0.170 s | 8.33 MiB | C++ |
 test |
100 | 0.200 s | 6.14 MiB | C++ |
 TooExcitetd |
100 | 0.204 s | 6.13 MiB | C++ |
 Sky_miner |
100 | 0.223 s | 8.68 MiB | C++ |
 gsj.cpp |
100 | 0.248 s | 21.00 MiB | C++ |
 Dedsec |
100 | 0.266 s | 5.75 MiB | C++ |
 _小妖 |
100 | 0.271 s | 6.13 MiB | C++ |
 TARDIS |
100 | 0.271 s | 7.18 MiB | C++ |
|
TooExcitetd |
100 | 0.275 s | 6.80 MiB | C++ |
| 本题关联比赛 | |||
| cmath生日赛 | |||
| 关于 膜拜 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题堆优化的dijkstra为什么不能过啊？
| ||||
|
爽啊 两天时间没了
rainy
2018-09-07 17:35
3楼
| ||||
|
测试数据看着真难受
 NVIDIA
2017-06-27 10:32
2楼
| ||||
|
Tarjan+SPFA+dp
| ||||
【题目描述】
有一个n个点m条边的有向图，xlm可以从1号点出发在图上走，并且最终需要回到1号点。每个点都有一个神犇（包括1号点），每次经过一个没到过的点，xlm都会膜拜那位神犇。xlm希望膜拜尽可能多的神犇。
由于xlm膜拜神犇的欲望非常强烈，所以他可以有一次机会逆着一条有向边的方向走。（需要注意的是，这条边的方向不会改变）
你现在想知道，xlm最多能膜拜多少神犇？
【输入格式】
输入到OrzOrz.in
第一行2个整数n、m，分别表示图的点数和边数。
第2行到底m+1行，每行两个整数u,v，描述一条u到v的有向边。
【输出格式】
输出到OrzOrz.out
一行一个整数表示xlm最多能膜拜多少神犇。
【样例输入】
7 10 1 2 3 1 2 5 2 4 3 7 3 5 3 6 6 5 7 2 4 7
【样例输出】
6
【提示】
【数据范围】
对于25%的数据，保证n<=100，m<=250，
对于43.75%的数据，保证n<=3,000，m<=7,000。
对于100%的数据，保证n,m<=100,000。
【来源】
QBXT春令营精英班第一次测试T2