/ Vijos / 题库 /

旅行计划

旅行计划

描述

在有N座城市的国度,Alice希望可以开始一场充满传奇的旅行。

TA希望可以从一个城市出发开始旅行,每次前往一个相邻的城市,途中不重复得经过恰好K座城市,最后抵达另外一个城市并结束旅行。
需要注意的是,起点与终点也被考虑为经过的城市,也就是说包括起点和终点在内经过的所有城市都是不能重复的。

现在,Alice希望知道哪些城市对<u,v>可以作为合法的旅行起点与终点。

格式

输入格式

本题每一个测试点有多组测试数据。第一行给定正整数T,表示数据组数。

之后,对于每一组数据来说,第一行给定三个整数N,M和K,表示城市个数,城市之间的相邻关系个数,还有旅途应该经过的城市个数。

之后M行,每一行给定两个整数u和v,表示标号为u的城市与标号为v的城市之间是相邻的,即可以从其中一个城市出发前往另外一个。

输出格式

对于每一组数据,输出N行,每行N个字符。

其中第i行第j个字符,或者为“Y”或者为“N”,分别表示是否存在从城市i出发到城市j结束的合法旅行方案。

样例1

样例输入1

1
5 6 4
1 2
2 3
3 5
1 4
4 5
2 5

样例输出1

NYYYY
YNNYY
YNNYN
YYYNY
YYNYN

限制

对于5%的数据,K<=2。
对于15%的数据,K<=3。
对于35%的数据,K<=4。
对于55%的数据,K<=5。
对于75%的数据,K<=6。
对于100%的数据,N<=1000,M<=5000,2<=K<=7且\(T\times \lfloor K/2\rfloor^{\lfloor K/2\rfloor} \le 60\)。

来源

SDOI 2015 round2 day1

信息

ID
1959
难度
9
分类
动态规划 点击显示
标签
递交数
119
已通过
7
通过率
6%
上传者

相关

在下列训练计划中:

RP++分类题库