@[lzqy_](/user/288716) 能否说一下大概的思路。
只看懂了拓扑+缩点,不太明白 bfs1 中的 `col[E[i].v]==c&&!vis[E[i].v]` 和 bfs2 中的 `col[e[i].v]==c&&!g[nxt(t.second)][e[i].v]`
还有主程序中
```cpp
if(g[j][x])
if(!M[mp(mp(col[x],col[e[i].v]),dis[e[i].v]+dis[x]+j)]){
Add(rt[col[x]],rt[col[e[i].v]],dis[e[i].v]+dis[x]+j);
M[mp(mp(col[x],col[e[i].v]),dis[e[i].v]+dis[x]+j)]=1;
}
```
是什么意思?
by andychen_2012 @ 2023-01-04 16:35:17
@[andychen_2012](/user/389192) 昂就是我在每个SCC里面钦定一个点为根,然后bfs1就是求出SCC中,每个点走到跟节点的距离(建反图从根开始bfs),bfs2就是用来求出g。g的意思是假设到根节点是周一,那么是否可以在周 $i$ 到达节点 $x$(保证同一SCC)。
主函数这里的话就是求是否能从一个SCC走向另一个SCC,然后M是防止连重复的边。
by lzqy_ @ 2023-01-04 17:00:08
不太会![](//图.tk/0)
套取了一下数据,发现数据中博物馆每周日程中为 $1$ 的只有下面这些点:
```
(1,5) (4,1) (4,7) (5,6) (6,3) (6,5) (11,3) (13,2) (13,7) (16,6)
(18,5) (23,1) (23,4) (24,4) (26,6) (29,1) (30,4) (30,7) (31,7) (33,6)
(33,7) (35,3) (37,4) (38,1) (38,5) (39,3) (39,4) (40,2) (43,2) (44,1)
(45,5) (45,7) (46,1) (46,7) (47,5) (48,6) (49,3) (51,5) (52,5) (53,3)
(53,7) (54,3) (54,7) (55,7) (56,3) (57,7) (58,4) (59,6) (61,4) (61,5)
(62,5) (69,5) (69,7) (70,6) (73,1) (74,2) (78,3) (82,1) (82,4) (86,3)
(87,7) (89,4) (89,7) (90,1) (92,2) (94,7) (95,5) (96,7) (97,1) (97,7)
(100,2)
```
括号中左边的数表示城市编号,右边的数表示一周中的第几天。
by andychen_2012 @ 2023-01-04 18:11:14
看起来或许是图的问题,这个看起来没什么问题
by andychen_2012 @ 2023-01-04 18:12:04
不会爬图,前几个大概长这样,每一行最左边表示起始点,右边的点都表示终止点:
```
1 36 25 19 52 45
2 14
3 74
4 82
5 1
6 26
7 44
9 52
10 6
11 81
12 11
13 38
14 23
15 75
16 27
17 28
19 85 58
20 67
21 93
22 10
23 70
24 18
25 69 77 37 80 73
26 46
27 92
28 21
29 32
30 88
31 13 24
32 99
33 100
34 29
35 5
36 59
37 22 60 54
38 20
39 55
40 25
41 40
42 22
43 41
44 89
45 51 34
46 98
47 51
48 30
49 2
50 78
51 12
52 97 56 86
53 42
55 57
57 73
59 4
60 48
61 87
62 84
63 35
64 72
65 64
```
如第一行表示 1->36,1->25,1->19,1->52,1->45。
by andychen_2012 @ 2023-01-04 18:23:52
感觉很正常,会不会是算法实现问题,比如说bitset爆了,这个点比较小,不太像数组爆了。
by andychen_2012 @ 2023-01-04 18:24:55
@[andychen_2012](/user/389192) 才看到/kk/kk
谢谢,我再调一调吧
by lzqy_ @ 2023-01-05 08:16:39
@[andychen_2012](/user/389192) 过了/ll
早上起来头脑清楚一点 发现有个小地方写错了
by lzqy_ @ 2023-01-05 08:36:35
@[lzqy_](/user/288716) 我对拍了好久都没找出问题,是哪里挂了呀?
by andychen_2012 @ 2023-01-05 14:02:06
@[andychen_2012](/user/389192) 昂就是133~135行,缩点完的图连边的时候,边权应该是 `dis[e[i].v]+j`,不用加 `dis[x]`
by lzqy_ @ 2023-01-05 17:20:24