logo AlgoBeat OnlineJudge
登录 注册

#215633. [ROIR 2015 Day 2] transform 魔法传送门

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

在一个王国里有 个城市,城市之间通过魔法传送门相连。

每对不同的城市之间有且仅有一个魔法传送门,允许从一个城市瞬间移动到另一个城市。

由于魔法传送门的特殊性质,每个传送门只能单向使用。对于每对城市 ,已知是否可以使用传送门从 或从

由于魔法传送门的特殊性,王国居民从一个城市到另一个城市时,有时需要使用多个传送门。此外,可能存在某些城市对之间不能通过任何魔法传送门到达。

王国的居民称一个城市为“完美城市”,如果可以仅使用魔法传送门从该城市到达王国的所有其他城市。假设初始时王国中有个完美城市。

最近国王决定选择一对城市,并将连接它们的传送门的方向反转。为了选择最佳方案,国王希望了解,通过调整一个传送门,王国中的完美城市数量可能发生的变化。

报告中包含对于每个整数 ,使得 ,满足以下条件的城市对 的数量:

  • 原始魔法传送门允许从城市 直接移动到城市
  • 如果将此魔法传送门的移动方向反转,使其允许从城市 直接移动到城市 ,则王国中完美城市的数量将变为

因此,部分报告仅包含那些通过调整传送门方向严格增加完美城市数量的方案。完整报告包含所有通过调整一个传送门的方向所得到的情况。

为了获取这些信息,国王计划向交通部请求相应的报告。国王可以请求部分报告或完整报告。报告的内容取决于参数 ,对于部分报告,,对于完整报告,

任务:编写一个程序,根据给定的魔法传送门方向信息生成相应的报告。

输入格式

输入文件的第一行包含两个整数: —— 王国中的城市数量 (), 时需要输出部分报告, 时需要输出完整报告。

接下来的 行包含 个字符,每行的第 个字符表示第 个城市与第 个城市之间的传送门情况:

  • “+”表示可以从城市 到城市
  • “-”表示可以从城市 到城市
  • “.”表示没有传送门(即 )。

输出格式

输出文件的第一行应包含一个整数 —— 王国中完美城市的数量。

如果需要部分报告(),则第二行应包含 个非负整数,按空格分隔,第 个数表示通过反转连接城市对 的传送门方向,可以使完美城市的数量变为 。如果 ,则第二行可以为空。

如果需要完整报告(),则第二行应包含 个非负整数,按空格分隔,第 个数表示通过反转连接城市对 的传送门方向,可以使完美城市的数量变为

样例

样例输入 1

5 0
.-+++
+.+++
--.+-
---.+
--+-.

样例输出 1

1
0 0 0 3

样例输入 2

5 1
.-+++
+.+++
--.+-
---.+
--+-.

样例输出 2

1
7 0 0 0 3

数据范围与提示

示例说明

在这个例子中,初始时,王国中只有城市 是完美的。通过反转连接城市 的传送门方向,所有城市都会变成完美城市。反转其他传送门仅使一个城市变成完美城市。

评分系统与子任务描述

子任务 1 (20 分)

子任务 2 (30 分)

子任务 3 (20 分)

子任务 4 (30 分)

翻译来源:GPT 5.2。