{"problem":{"name":"[湖北省选模拟 2023] 环山危路 / road","description":{"content":"R 国有 $n$ 座城市，编号从 $1$ 到 $n$。这些城市两两之间都有道路连接，形成一个图的结构。不过，这些路修得很烂，每条路都有一个固定的方向，车只能按照这个方向行驶；路还是一次性的，也就是说最多只能过一辆车。 现在 R 国正在制定防灾减灾预案。你需要帮助 R 国计算，如果 $t_i$ 号城市发生了灾难，并且 $s_{i,1},s_{i,2},\\dots,s_{i,k_i}$ 这些城市有充","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9545"},"statements":[{"statement_type":"Markdown","content":"R 国有 $n$ 座城市，编号从 $1$ 到 $n$。这些城市两两之间都有道路连接，形成一个图的结构。不过，这些路修得很烂，每条路都有一个固定的方向，车只能按照这个方向行驶；路还是一次性的，也就是说最多只能过一辆车。\n\n现在 R 国正在制定防灾减灾预案。你需要帮助 R 国计算，如果 $t_i$ 号城市发生了灾难，并且 $s_{i,1},s_{i,2},\\dots,s_{i,k_i}$ 这些城市有充足的救灾物资（可以认为它们都拥有可以装无数辆车的物资），那么最多能从这些城市运送几车物资到达 $t_i$。车只能走城间的那些一次性道路，不过车在到达 $t_i$ 之前是可以经过多个城市和多条道路中转的。\n\n## Input\n\n输入共 $n+m +1$ 行。\n\n第一行两个正整数 $n,m$，表示城市个数和询问次数。\n\n第二行到第 $n+1$ 行，每行一个长为 $n$ 的 $01$ 字符串，第 $i+1$ 行第 $j$ 列表示是否有从 $i$ 通向 $j$ 的道路（$1$ 表示有，$0$ 表示无）。\n\n接下来 $m$ 行，每行第一个正整数为 $t_i$，第二个正整数为 $k_i$，接着 $k_i$ 个正整数 $s_{i,1},s_{i,2},\\dots,s_{i,k_i}$。保证 $s_{i,1},s_{i,2},\\dots,s_{i,k_i}$ 中没有重复的数且没有 $t_i$。\n\n## Output\n\n输出 $m$ 行，每行一个非负整数，表示第 $i$ 次询问的答案。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n城市间的路如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/3he9r0j2.png)\n\n这是答案对应的一种可能的方案：\n\n第一次询问中，一辆车走 $1 \\rightarrow 2$，另一辆走 $4 \\rightarrow 1 \\rightarrow 5 \\rightarrow 2$；\n\n第二次询问中，一辆车走 $1 \\rightarrow 5$，一辆走 $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow5$，还有一辆走 $4 \\rightarrow 5$。\n\n### 子任务\n\n对于所有测试数据，保证 $1 \\le n \\le 3000$，$1 \\le m,\\sum\\limits_{i=1}^mk_i \\le 30000$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/d7a2om1c.png)\n\n特殊性质 A：保证所有询问的 $t_i$ 相等。\n\n特殊性质 B：保证 $u$ 与 $v$ 之间的路从 $\\min(u,v)$ 通向 $\\max(u,v)$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9545","tags":["2023","O2优化","湖北"],"sample_group":[["5 2\n01001\n00110\n10001\n10101\n01000\n2 2 1 4\n5 2 4 1\n","2\n3\n"],["见选手目录下的 road/road2.in 与 road/road2.ans。","见选手目录下的 road/road2.in 与 road/road2.ans。"]],"created_at":"2026-03-03 11:09:25"}}