[GESP样题七级] 迷宫统计

Luogu

IDLGP10265

Time1000ms

Memory128MB

DifficultyP2

图论GESP

在神秘的幻想⼤陆中，存在着 $n$ 个古老而神奇的迷宫，迷宫编号从 $1$ 到 $n$。有的迷宫之间可以直接往返，有的可以⾛到别的迷宫，但是不能⾛回来。玩家小杨想挑战⼀下不同的迷宫，他决定从 $m$ 号迷宫出发。现在，他需要你帮助他统计：有多少迷宫可以直接到达 $m$ 号迷宫，$m$ 号迷宫可以直接到达其他的迷宫有多少，并求出他们的和。需要注意的是，对于 $i$ ($1 \leq i \leq n$) 号迷宫，它总可以直接到达自身。 ## Input 第一行两个整数 $n$ 和 $m$，分别表示结点迷宫总数，指定出发迷宫的编号。下面 $n$ 行，每行 $n$ 个整数，表示迷宫之间的关系。对于第 $i$ 行第 $j$ 列的整数，$1$ 表示能从 $i$ 号迷宫直接到达 $j$ 号迷宫，$0$ 表示不能直接到达。 ## Output 一行输出空格分隔的三个整数，分别表示迷宫 $m$ 可以直接到达其他的迷宫有多少个，有多少迷宫可以直接到达 $m$ 号迷宫，这些迷宫的总和。 [samples] ## Background 对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1107> ## Note ### 样例 1 解释 $4$ 号迷宫能直接到达的迷宫有 $3,4,6$ 号迷宫，共 $3$ 个。能直接到达 $4$ 号迷宫的迷宫有 $1,4,5$ 号迷宫，共 $3$ 个。共 6 个。 ### 数据规模与约定 | 子任务| 分值 | $n \leq $ | | :-: | :-: | :-: | | $1$ | $30$ | $10$ | | $2$ | $30$ | $100$ | | $3$ | $40$ | $1000$ | 对全部的测试数据，保证 $1 \leq m \leq n \leq 1000$。

Samples

Input #1

6 4
1 1 0 1 0 0
0 1 1 0 0 0
1 0 1 0 0 1
0 0 1 1 0 1
0 0 0 1 1 0
1 0 0 0 1 1

Output #1

3 3 6

API Response (JSON)

{
  "problem": {
    "name": "[GESP样题 七级] 迷宫统计",
    "description": {
      "content": "在神秘的幻想⼤陆中，存在着 $n$ 个古老而神奇的迷宫，迷宫编号从 $1$ 到 $n$。有的迷宫之间可以直接往返，有的可以⾛到别的迷宫，但是不能⾛回来。玩家小杨想挑战⼀下不同的迷宫，他决定从 $m$ 号迷宫出发。现在，他需要你帮助他统计：有多少迷宫可以直接到达 $m$ 号迷宫，$m$ 号迷宫可以直接到达其他的迷宫有多少，并求出他们的和。 需要注意的是，对于 $i$ ($1 \\leq i \\leq",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10265"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在神秘的幻想⼤陆中，存在着 $n$ 个古老而神奇的迷宫，迷宫编号从 $1$ 到 $n$。有的迷宫之间可以直接往返，有的可以⾛到别的迷宫，但是不能⾛回来。玩家小杨想挑战⼀下不同的迷宫，他决定从 $m$ 号迷宫出发。现在，他需要你帮助他统计：有多少迷宫可以直接到达 $m$ 号迷宫，$m$ 号迷宫可以直接到达其他的迷宫有多少，并求出他们的和。\n\n需要注意的是，对于 $i$ ($1 \\leq i \\leq...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments

[GESP样题 七级] 迷宫统计

[GESP样题七级] 迷宫统计