这题有点问题
  • 板块P2194 HXY烧情侣
  • 楼主ipLee
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/10/22 22:40
  • 上次更新2023/11/5 10:08:22
查看原帖
这题有点问题
362594
ipLee楼主2020/10/22 22:40

如果一个电影院可以经过多次、并且没有要求路径最短的话,实际上方案数远远大于SCC内点权最小的点数和

以下为例

8
1 2 2 2 1 2 2 2
10
1 2
2 3
3 4
4 1
2 8
7 3
5 6
6 7
7 8
8 5

这个图是分为外圈和内圈的,内外圈用282\to 8737\to 3分割。如果是标程的话答案是2,但是实际上有至少三种方案数:

  • 1,2,3,4,1,2,8,5,61,2,3,4,1,2,8,5,6
  • 1,2,8,7,5,6,7,3,41,2,8,7,5,6,7,3,4
  • 5,6,7,3,4,1,2,85,6,7,3,4,1,2,8

可以看出,完全可以重复经过同一个点达到刷方案数的目的

建议修改题面

2020/10/22 22:40
加载中...