#P8084. 「COCI 2015.3」JANJE
「COCI 2015.3」JANJE
题目描述
年轻的 Bojan 现在是一名成功的电气工程专业学生,从小就喜欢涂色。想起童年时漫不经心的日子,他决定买一本涂色书和 种颜色的颜料,然后开始工作。有趣的是,Bojan 不喜欢五颜六色的图片,所以他决定每张图片最多使用三种不同的颜色着色。此外,Bojan 永远不会用同一种颜色给两个相邻的区域上色,如果两个区域的边缘至少有一个连接点,则被视为相邻。例如,下图用 和 表示的区域是相邻的,而区域 和 则不是。此外,下面这张图片的着色方式符合 Bojan 的所有要求。

在开始给一张图片上色之前,Bojan 会问自己有多少种方法可以给这张图上色,从而满足他的所有条件。鉴于 Bojan 是学电气工程的,可以理解的是,组合学不是他的强项,所以他向你寻求帮助。
输入格式
输入仅一行两个整数 ,分别代表涂色书里面的图片编号和 Bojan 的颜料拥有的颜色数量。
涂色书将会在附件中给出(即文件 Happy coloring book.pdf,请点击页面右侧的「文件」按钮查看),涂色书里面的图片按照先后顺序依次编号为 到 。
输出格式
输出仅一行一个整数,代表 Bojan 在满足自己所有要求的上色方式的个数。只要至少有一个区域的颜色不同,就视为不同的上色方式。
2 2
0
5 3
12
7 3
96
数据范围与提示
对于所有数据,,。
图片对应的邻接图
以下是原涂色书图片的文字索引。每个顶点代表一个需要上色的区域,每条无向边代表一对相邻区域。未列出的区域对不相邻,图片外部的背景不参与上色。
- 毛毛虫:20 个区域组成一条链。从头到尾编号 至 ,边为 ()。眼睛、触角和脸部的线条不是独立的涂色区域。
- 海边小屋:顶点 1 为墙面,2 为门,3、4 为一扇窗的两格,5、6 为另一扇窗的两格,7 为屋顶,8 为屋顶内的圆。边为 ()以及 。
- 标志:顶点 1 为大圆内扣除两个小区域后的部分,另外三个区域是大圆外侧的框内区域和圆内的两个小区域。边为 。
- 雪人:顶点 1 为帽子,顶点 2 至 5 依次为从上到下的四个圆形区域(不含内部纽扣)。边包括链 。顶点 3、4、5 上分别有 2、3、4 个纽扣,每个纽扣是只与所在圆相邻的一个顶点。
- 抽象球:顶点 1、2 为外环的上、下两部分,顶点 3 为中间完整的环,顶点 4、5 为内圆的上、下两部分。边为 。
- 金字塔:从上往下有 10 行,第 行有 块砖。顶点 是该行从左数第 块。同一行的相邻砖块连边;若 , 还和下一行的 连边。
- 雏菊:顶点 1 为茎,2 为花盆,3、4 为一片叶的两半,5、6 为另一片叶的两半,7 为花瓣连成的区域,8 为花心。邻接边与图 2 的编号完全相同。
- 蹦床:30 个白色区域构成一个环,按圆周顺序编号,边为 ()及 。灰色内部不参与上色。