蒜头君的蜡笔

62 阅读 0 评论 41 点赞

我是靠谱客的博主俏皮芒果，最近开发中收集的这篇文章主要介绍蒜头君的蜡笔，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

蒜头君收到了一个生日礼物——一盒精美的蜡笔，这可把他高兴坏了。蒜头君在完成一道图论的题目后，拿着蜡笔想给题目上的一个无向图进行填色。无向图上一共有 $n$ 个点，编号从 $0$ 到 $n - 1$ ，那么该图就会有 $2^n - 1$ 个非空子图。

蒜头君想给每 $i$ 个子图进行填色，使得任意一条边连接的两个点的颜色不同，现在他想知道给第 $i$ 个子图填色，最少需要多少种不同的颜色，记为 $s_i$ 。蒜头君想请你帮他计算一下以下式子的结果：

$sum_{i = 1}^{2^n-1} s_i times 233^{i}.$

输入格式

第一行输入一个整数 $n$ （ $1 \leq n \leq 16$ ），表示无向图有 $n$ 个点。

接下来输入一个 $n \times n$ 的 $01$ 矩阵，表示无向图边的情况。如果 $a [i] [j] = 1$ ，则说明 $i$ 与 $j$ 之间有边相连，如果 $a [i] [j] = 0$ ，则表示 $i$ 与 $j$ 之间没有边相连。

输出格式

输出一行，输出上述式子的结果，结果可能会很大，输出结果对 $2^{32}$ 取余的结果即可。

样例输入

样例输出

1595912448

解题说明：初始化出所有只涂一个颜色的子图。记这样的子图dp[i]=1;节点少的子图去更新节点都的子图，

dp[i]=min(dp[i],dp[j^i]+dp[j]);图的两个子图集的涂色数相加。比如1-2-3-4-5-6这样的图，我们预处理时会得到dp[图：1-3-5]=1,dp[图：2-4-6]=1

那么dp[1-2-3-4-5-6]更新时就会变成2；

没啥说的，这题卡了我好久！本地对了就是对了，线上提交错误说明oj有问题！。。。。。我忘记初始了。每轮i循坏mn都需要置为无穷大，见鬼了。

AC代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
int dp[1<<16];
int a[20][20];
bool mark[1<<16];
unsigned int powdiy(int x,int y){
unsigned int re=1,be=x;
while(y){
if(y&1)re*=be;
be*=be;
y>>=1;
}
return re;
}
void judge(int x){
int tot=1;
int cot=0;
int note[20];
int temp=x;
while(x){
if(x&1){
note[cot++]=tot;
}
x>>=1;
tot++;
}
for(int i=0;i<cot-1;i++)
for(int j=i+1;j<cot;j++){
if(a[note[i]][note[j]]){
return ;
}
}
dp[temp]=1;
return ;
}
unsigned int
sum=0;
int main(){
int n;cin>>n;
memset(dp,inf,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
scanf("%1d",&a[i][j]);
}
for(int i=1;i<(1<<n);i++){
judge(i);
}
for(int i=1;i<(1<<n);i++){
int mn=inf;
for(int j=i;j;j=(j-1)&i){
dp[i]=min(dp[i],dp[j^i]+dp[j]);
mn=min(dp[i],mn);
}
sum+=(mn*powdiy(233,i));
}
cout<<sum<<endl;
return 0;
}