首页 > 代码库 > HDU5823 color II
HDU5823 color II
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.
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.
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}.
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
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。