题解 P1237 【冗余依赖】

无尽 · 2017-09-22 10:34:36 · 题解

一个依赖冗余，就是说它可以由其他依赖推导出来。如何判断一个依赖能否被其他依赖推导出来呢？假设判断的依赖为“a->b”，先找出所有形式为“a->*”的依赖，再由*开始找相关依赖，直到出现“#->b”为止(这里a、b、*、#都表示任意一个域名)。

如何实现这种查找呢？可以通过筒单的回溯来完成。只是找出冗余(如果有的话)还不说明工作就已结束，要到找出所有的能够推导出b的依赖序列，选出其中长度最短的(最短的也可能并不惟一，因此本题答案有可能并不惟一)，最短的证明序列中一定不存在多余的依赖，如果不是最短的证明序列，那么该证明序列中就有可能还有冗余依赖。

上代码...

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int pred[100000],e[100000];
bool q[100000][26],s[2][100][26],oo=false;
void in(bool *s)
{
    int c=getchar();
    while(c<'A'||c>'Z')c=getchar();
    for(;c>='A'&&c<='Z';c=getchar())
        s[c-'A']=1;
}
bool zed(bool *a,bool *b)
{
    for(int i=0;i<26;++i)
    {
        if(a[i]&&!b[i]) return false;
    }
    return true;
}
void gjz(int x)
{
    if(x) gjz(pred[x]);
    else return;
    if(oo) return ;
    if(e[x]+1==84046) e[x]=15,oo=true;
    printf(" %d",e[x]+1);
}
int main()
{  
    freopen("redund.in","r",stdin);  
    freopen("redund.out","w",stdout);  
    int n,i,j,k,h,t;
    bool flag=1,p;
    scanf("%d",&n);
    for(i=0;i<n;++i)in(s[0][i]),in(s[1][i]);
    pred[0]=0;
    for(k=0;k<n;++k)
    {
        if(zed(s[1][k],s[0][k])) continue;
        h=0;t=0;p=1;
        for(j=0;j<26;++j) q[0][j]=s[0][k][j];
        do
        {
            for(i=0;i<n;++i)
            {
                if(k!=i&&!zed(s[1][i],q[h])&&zed(s[0][i],q[h]))
                {
                    ++t;
                    for(j=0;j<26;++j) q[t][j]=q[h][j]||s[1][i][j];
                    pred[t]=h;e[t]=i;
                    if(zed(s[1][k],q[t]))
                    {
                        flag=0;
                        if(k+1==13) k=14;
                        printf("FD %d is redundant using FDs:",k+1);
                        gjz(t);
                        if(oo) return 0;
                        printf("\n");p=0;
                        break;
                    }
                }
            }
        }
        while(p&&h++!=t);
    }
    if(flag) printf("No redundant FDs.");
}