TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4365
  • 题目
  • P4365染色
    限制 : 时间限制 : 2000 MS   空间限制 : 65536 KB
    问题描述

    原始题面

    ou are given an undirected graph with n vertices numbered 0 through n-1.

    Obviously, the vertices have 2^n - 1 non-empty subsets. For a non-empty subset S, we define a proper coloring of S is a way to assign each vertex in S a color, so that no two vertices in S with the same color are directly connected by an edge. Assume we've used k different kinds of colors in a proper coloring. We define the chromatic number of subset S is the minimum possible k among all the proper colorings of S.

    Now your task is to compute the chromatic number of every non-empty subset of the n vertices.

    输入格式

    First line contains an integer t. Then t testcases follow.

    In each testcase: First line contains an integer n. Next n lines each contains a string consisting of '0' and '1'. For 0<=i<=n-1 and 0<=j<=n-1, if the j-th character of the i-th line is '1', then vertices i and j are directly connected by an edge, otherwise they are not directly connected.

    The i-th character of the i-th line is always '0'. The i-th character of the j-th line is always the same as the j-th character of the i-th line.

    For all testcases, 1<=n<=18. There are no more than 100 testcases with 1<=n<=10, no more than 3 testcases with 11<=n<=15, and no more than 2 testcases with 16<=n<=18.

    输出格式

    样例输入

    2
    4
    0110
    1010
    1101
    0010
    4
    0111
    1010
    1101
    1010

    样例输出

    1022423354
    2538351020

    提示
    第一组数据, ans[1..15]= {1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2, 3}

    来源  udh 3285