← 返回题目

题库练习旅行计划

← 上一题下一题 →

A2761 | $旅行计划$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在有 $N$ 座城市的国度，Alice 希望可以开始一场充满传奇的旅行。TA 希望可以从一个城市出发开始旅行，每次前往一个相邻的城市，途中不重复得经过恰好 $K$ 座城市，最后抵达另外一个城市并结束旅行。 需要注意的是，起点与终点也被考虑为经过的城市，也就是说包括起点和终点在内经过的所有城市都是不能重复的。现在，Alice 希望知道哪些城市对 $(u,v)$ 可以作为合法的旅行起点与终点。

输入格式

本题每一个测试点有多组测试数据。 第一行给定正整数 $T$ ，表示数据组数。 对于每一组数据来说，第一行给定三个整数 $N$，$M$ 和 $K$，表示城市个数，城市之间的相邻关系个数，还有旅途应该经过的城市个数。 接下来 $M$ 行．每一行给定两个整数 $u$ 和 $v$ ，表示标号为 $u$ 的城市与标号为 $v$ 的城市之间是相邻的，即可以从其中一个城市出发前往另外一个。 $N\le 1000$，$M\le 5000$，$2\le K\le 7$ 且 $T\times \left\lfloor \frac k 2 \right\rfloor^{\left\lfloor \frac k 2 \right\rfloor}\le 60$

输出格式

对于每一组数据，输出 $N$ 行，每行 $N$ 个字符，其中第 $i$ 行第 $j$ 个字符，或者为 Y 或者为 N ，分别表示是否存在从城市 $i$ 出发到城市 $j$ 结束的合法旅行方案。

输入输出样例

输入 #1

输出 #1

NYYYY 
YNNYY 
YNNYN 
YYYNY 
YYNYN

C++ 编辑器

输入

输出