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

概述

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

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

displaystyle sum_{i = 1}^{2^n-1} s_i times 233^{i}.i=12n1si×233i.

输入格式

第一行输入一个整数 nn1leq nleq 161n16),表示无向图有 nn 个点。

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

输出格式

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

样例输入

4
0111
1011
1101
1110

样例输出

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;
}

最后

以上就是俏皮芒果为你收集整理的蒜头君的蜡笔的全部内容,希望文章能够帮你解决蒜头君的蜡笔所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(40)

评论列表共有 0 条评论

立即
投稿
返回
顶部