P2819 图的m着色问题

    • 1.3K通过
    • 2.2K提交
  • 题目提供者 zyg20010121
  • 评测方式 云端评测
  • 标签 搜索 模拟 递归 高性能
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法。

    题目描述

    对于给定的无向连通图G和m种不同的颜色,编程计算图的所有不同的着色法。

    输入输出格式

    输入格式:

    第1行有3个正整数n,k 和m,表示给定的图G有n个顶点和k条边,m种颜色。顶点编号为1,2,…,n。接下来的k行中,每行有2个正整数u,v,表示图G 的一条边(u,v)。

    输出格式:

    程序运行结束时,将计算出的不同的着色方案数输出。

    输入输出样例

    输入样例#1: 复制
    5 8 4
    1 2
    1 3
    1 4
    2 3
    2 4
    2 5
    3 4
    4 5
    输出样例#1: 复制
    48

    说明

    n<=100;k<=2500;

    在n很大时保证k足够大。

    保证答案不超过20000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。