【状态压缩DP】函数依赖
发布时间:2020-12-13 20:05:37 所属栏目:百科 来源:网络整理
导读:函数依赖 【问题描述】 设 R(U)是一个属性集 U 上的关系模式,X 和 Y 是 U 的子集。若对于 R(U) 的任意一个可能的关系 r,r 中不可能存在两个元组在 X 上的属性值相等,而在 Y 上的属性值不等, 则称 “X 函数确定 Y” 或 “Y 函数依赖于 X” ,记作 X →Y。
函数依赖
【问题描述】 设 R(U)是一个属性集 U 上的关系模式,X 和 Y 是 U 的子集。若对于 R(U) 的任意一个可能的关系 r,r 中不可能存在两个元组在 X 上的属性值相等,而在 Y 上的属性值不等, 则称 “X 函数确定 Y” 或 “Y 函数依赖于 X” ,记作 X →Y。其中X称为这个函数依赖的决定属性集(Determinant)。 解释:如果有函数依赖 X?Y,当我们知道 X 的时候,也就知道了 Y,也就 是 X能推出 Y。另外,可以简单的证明,如果 X?Y,Y?Z,那么可以得到 X?Z。 若关系中的某一属性组的值能唯一的表示一个元组,则称该属性组为超码。 若关系中的某一属性组的值能唯一地表示一个元组,而其真子集不行,则称 该属性组为候选码。 解释:设有属性集合(A,B,C)和函数依赖 A?B和 B?C,显然,在已知 A 的 情况下,我们能够通过函数依赖得到整个集合的所有属性 ABC,那么我们称 A 为超码。当超码的任何一个子集都不是超码的时候,我们称之为候选码。例如 AB是一个超码,但是不是一个候选码,因为A 是 AB的子集,它也是超码。 现在给出属性集合和函数依赖集合R(U,F),请找出该 R 的候选码。 【输入文件】 输入文件的第一行为一个整数N(N ≤ 10)和 M(1 ≤ M ≤ 1000),表示属性集中 的属性个数和函数依赖集中的依赖个数。这里我们默认大写字母中的前 N 个字 母为我们所考虑的属性。接下来的 M 行每行一个字符串表示一个函数依赖,如 AB?DE。(中间的蕴含符号是由减号和大于号组成。另外需要说明的是,只有当 我们同时得到 A和 B 的时候,才能推出D和 E) 。 【输出文件】 输出文件的第一行希望你输出你找到的候选码的个数K。 接下来的 K行每行 输出一个候选码。候选码本身按字母顺序排列,所有候选码按照字典顺序排列输 出。如果没有找到候选码,输出“No candidate key”(不含引号)。 【样例输入】 5 5 AB->C AC->B AD->E BC->D E->A 【样例输入】 首先注意。。那个No candidate key是坑爹的。。最坏都是候选码为ABCD...J。 所以想靠输无解来骗10分的童鞋自重。。
用位集合来表示,A∩B=B,则B∈A。 要注意一个问题,一开始输入的时候可能会有这种问题,AA,BB这之类的,我一开始用的加法就错了,应该或运算
DFS超时一组,其他的秒过,状态空间太大了。如果用枚举就能全过(类似Bellman-Ford,从头扫描到尾多次,直到不能不能再继续延续下去,这种思路比较好。见后面) #include <cstdio> #include <cstring> #include <algorithm> long ans[1050]; char ans2[1050][15]; long top = 0; long N;long M; long from[1005]; long to[1005]; bool hash[1050]; bool dfs(long sta) { if (sta == (1<<N)-1) return true; for (long i=1;i<M+1;i++) { if ((sta&from[i])==from[i]) { if (!hash[sta|to[i]] && (sta|to[i])-sta && !hash[sta|to[i]]) { hash[sta|to[i]] = true; if (dfs(sta|to[i])) { hash[sta|to[i]] = false; return true; } hash[sta|to[i]] = false; } } } return false; } void Trans(long b) { long a = ans[b]; long p = 0; long s = 0; do{ if (a & 1) ans2[b][++s]=p+'A'; p ++; }while (a>>=1); } int cmpare(const void *aa,const void *bb) { char * a = (char*) aa; char * b = (char*) bb; long len = 0; while (a[++len] && b[len]) { if (a[len] > b[len]) return 1; if (a[len] < b[len]) return -1; } if (a[len] > b[len]) return 1; if (a[len] < b[len]) return -1; return 0; } int main() { freopen("dependence.in","r",stdin); freopen("dependence.out","w",stdout); scanf("%ld%ld",&N,&M); for (long i=1;i<M+1;i++) { char tmp[30]; char tmp2[15]; tmp[0] = tmp2[0] = 0; scanf("%s",tmp+1); long ff=0;long tt=0; while (tmp[++tmp[0]]-'-'){ff|=(1<<(tmp[tmp[0]]-'A'));} tmp[0]++; while (tmp2[++tmp2[0]]=tmp[++tmp[0]]){tt|=(1<<(tmp2[tmp2[0]]-'A'));} from[i] = ff; to[i] = tt; } for (long i=0;i<(1<<N);i++) { bool flag = false; for (long j=1;j<top+1;j++) if ((ans[j]&i) == ans[j]) {flag=true;break;} hash[i] = true; if (!flag && dfs(i)) ans[++top] = i; hash[i] = false; } printf("%ldn",top); for (long i=1;i<top+1;i++) Trans(i); qsort(ans2+1,top,sizeof(ans2[0]),cmpare); for (long i=1;i<top+1;i++) printf("%sn",ans2[i]+1); return 0; }
以下是AC程序 #include <cstdlib> #include <cstdio> long N;long M; long from[1005]; long to[1005]; long ans[1050]; char ans2[1050][15]; long top = 0; void Trans(long x) { long p = 0; long q = 0; long l = ans[x]; do{ if (l&1) { ans2[x][++q]=p+'A'; } p ++; }while (l >>= 1); } int cmpare(const void* aa,const void* bb) { char * a = (char*) aa; char * b = (char*) bb; long len = 0; while (a[++len] && b[len]) { if (a[len] > b[len]) return 1; if (a[len] < b[len]) return -1; } if (a[len]) return 1; if (b[len]) return -1; return 0; } int main() { freopen("dependence.in",stdout); scanf("%ld%ld",&M); for (long i=1;i<M+1;i++) { char tmp[30]; tmp[0] = 0; scanf("%s",tmp+1); long ff = 0; while (tmp[++tmp[0]]-'-') ff |= (1<<(tmp[tmp[0]]-'A')); tmp[0]++; long tt = 0; while (tmp[++tmp[0]]) tt |= (1<<(tmp[tmp[0]]-'A')); from[i] = ff; to[i] = tt; } for (long Start=0;Start<(1<<N);Start++) { bool fflag = false; for (long i=1;i<top+1;i++) if ((ans[i]&Start)==ans[i]) fflag = true; if (fflag) continue; long sta = Start; while (sta < (1<<N)) { bool flag = false; for (long i=1;i<M+1;i++) { if ((sta|to[i])!=sta && (sta&from[i])==from[i]) { sta |= to[i]; flag = true; } } if (!flag) break; } if (sta == (1<<N)-1) ans[++top] = Start; } for (long i=1;i<top+1;i++) { Trans(i); } qsort(ans2+1,cmpare); printf("%ldn",top); for (long i=1;i<top+1;i++) { printf("%sn",ans2[i]+1); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |