HDU5823 color II

时间：2016-10-03 21:25:38 阅读：246 评论：0 收藏：0 [点我收藏+]

Time Limit: 2000MS

Memory Limit: 65536KB

64bit IO Format: %I64d & %I64u

Description

You 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.

Input

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.

Output

For each testcase, only print an integer as your answer in a line.

This integer is determined as follows:
We define the identity number of a subset S is

Sample Input

Sample Output

1022423354
2538351020

Hint

For the first test case, ans[1..15]= {1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2, 3}

Source

2016 Multi-University Training Contest 8

统计每个子集的最小染色数，按公式算就行了。

模拟染色是行不通的，因为在同一个图中根据不同的染色顺序，可能得出不同的答案。

正解是状压DP。

先预处理出每个子集是不是独立集，然后尽量把独立集中的点都染上同一个颜色，这样的染色方法是最优的。

然后在不同的独立集之间状态转移即可。

位运算大法好，位运算大法好。

 1 /*by SilverN*/
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #define LL long long
 8 using namespace std;
 9 const LL mod=4294967296;
10 const int mxn=320000;
11 int read(){
12     int x=0,f=1;char ch=getchar();
13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
15     return x*f;
16 }
17 int f[mxn];
18 int n;
19 LL ans;
20 int mp[20];
21 bool inv[mxn];
22 int main(){
23     int T;
24     T=read();
25     int i,j;
26     while(T--){
27         memset(mp,0,sizeof mp);
28         memset(f,0,sizeof f);
29         memset(inv,0,sizeof inv);
30         ans=0;
31         n=read();
32         char ch[30];
33         int ed=(1<<n);
34         for(i=0;i<n;++i){
35             scanf("%s",ch);
36             for(j=0;j<n;++j){
37                 if(ch[j]==‘1‘)mp[i]|=(1<<j);
38             }
39         }
40         
41         for(int s=1;s<ed;++s){
42             bool flag=1;
43             for(i=0;i<n;++i){
44                 if(s&(1<<i)){
45                     if(s & mp[i]){
46                         flag=0;
47                         break;
48                     }
49                 }
50             }
51             inv[s]=flag;
52         }
53         for(int s=1;s<ed;++s){
54             int tmp=1e6;
55             for(i=s;i;i=(i-1)&s){
56                 if(inv[i]){
57                     tmp=min(tmp,f[s^i]+1);
58                 }
59             }
60             f[s]=tmp;
61         }
62         LL tmp=1;
63         for(i=1;i<ed;i++){
64             tmp=(tmp*233)%mod;
65             ans=(ans+tmp*f[i])%mod;
66         }
67         printf("%lld\n",ans);
68     }
69     return 0;
70 }

HDU5823 color II

原文：http://www.cnblogs.com/SilverNebula/p/5929550.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)