[xsy2300]好题
2024-09-03 01:21:47
题意:有一棵树,每个节点有颜色,要找出最小的连通块使得其中的点至少有$k$种不同的颜色,只需输出这个最小连通块的大小
因为$k$很小,所以如果颜色只有$k$种,我们可以直接状压DP,设$f_{i,j}$表示在$i$的子树中包含颜色集合为$j$的最小连通块大小(这个连通块必须包含$i$),那么可以枚举$s$的子集$t$,转移即为$f_{x,s}\gets f_{x,t}+f_{u,s-t}\left(u\in son_x\right)$
但颜色最多有$n$种,这时候我们就可以trick一下:随机地把$n$种颜色映射到$k$种颜色再DP,随机多几次错误的概率就很低了
......但我第一次交还是WA了啊==同样的代码再交一次就A了(论一个非洲人的自我修养)
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<time.h> int min(int a,int b){return a<b?a:b;} int h[10010],nex[20010],to[20010],c[10010],p[10010],f[10010][32],M,k; void add(int a,int b){ M++; to[M]=b; nex[M]=h[a]; h[a]=M; } void dfs(int fa,int x){ int i,s,t; f[x][p[c[x]]]=1; for(i=h[x];i;i=nex[i]){ if(to[i]!=fa){ dfs(x,to[i]); for(s=0;s<1<<k;s++){ for(t=s;t;t=(t-1)&s)f[x][s]=min(f[x][s],f[x][t]+f[to[i]][s^t]); } } } for(s=0;s<1<<k;s++){ for(t=s;t;t=(t-1)&s)f[x][t]=min(f[x][t],f[x][s]); } } int main(){ srand(time(0)); int T,n,i,x,y,ans; scanf("%d%d",&n,&k); for(i=1;i<=n;i++)scanf("%d",c+i); for(i=1;i<n;i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } T=50; ans=n; while(T--){ for(i=1;i<=n;i++)p[i]=1<<(rand()%k); memset(f,63,sizeof(f)); dfs(0,1); for(i=1;i<=n;i++)ans=min(ans,f[i][(1<<k)-1]); } printf("%d",ans); }
最新文章
- 简单阐述下OC中UIImage三种创建方式~~~
- Android驱动开发前的准备(四)
- mysql5.7 代价模型浅析
- 解剖SQLSERVER 第十二篇 OrcaMDF 行压缩支持(译)
- LaTex学习笔记(一):review
- 解决";java.lang.ClassNotFoundException: com.mysql.jdbc.Driver";
- 初试visual studio2012的新型数据库LocalDB
- C语言中.h和.c文件解析(很精彩)
- 20140708郑州培训第二题Impossible Game
- jQuery实现公告文字左右滚动的代码。
- .net 微信APP支付接口的开发流程以及坑
- __x__(14)0906第三天__<;iframe>; 内联框架 引入有一个外部html页面
- 安全之路 —— 使用Windows全局钩子打造键盘记录器
- YARN Resource Management
- 最新案例铁血军事手机客户端(IOS &; Android)
- Java基础五(方法)
- vorpal 又一个方便的cli 开发包
- PHP数组对象互转
- CRC校验3种算法_转载
- map的put和putIfAbsent使用