首页 > 代码库 > HDU5823 color II

HDU5823 color II

2024-08-15 14:32:44   219人阅读

 

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 id(S)=\sum_{v\in S} 2^v. Let the chromatic number of S be f_{id(S)}. 

You need to output \sum_{1<=id(S)<=2^n - 1} f_{id(S)} \times 233^{id(S)} \mod 2^{32}.

Sample Input

24011010101101001040111101011011010

Sample Output

10224233542538351020

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


联系
我们