地铁换乘

发布时间 2023-12-27 20:29:24作者: 小超手123

题意:

\(n\)个地铁站和 \(m\) 条地铁线路。给定 \(n \times m\)\(01\) 矩阵 \(a\),第 \(i\) 条地铁线路连接 所有满足 $a_{j,i} = 1 $ 的地铁站 \(j\)。每条地铁线路连接的地铁站可以互相到达。

找到最长的区间 \([l, r]\) 满足 \(∀i, j ∈ [l, r]\)\(i\) 可以仅经过编号为 \(l, l + 1, · · · , r\) 的地铁站,通过若干次换乘到达 \(j\)

分析:

一种简单的暴力做法是,枚举左右端点 \(l,r\),然后用并查集实时维护联通块数量。

考虑如何优化,注意到 \(m \le 500\)可以把每条线路看成一个点,连接两条线路的地铁站看成一条边。具体的,把存在于 \([l,r]\) 内的所有点(路线)看成一个图的点集,把 \([l,r]\) 内的所有地铁站所构成的边看成一个图的边集,\([l,r]\) 为符合答案的区间当且仅当联通块数量为 \(1\)

考虑 \([l,r]\) 为合法的时候,由于题目保证每个地铁站内有至少一条地铁线路

施工中
施工中
施工中
施工中