4160: [Neerc2009]Exclusive Access 2

http://www.lydsy.com/JudgeOnline/problem.php?id=4160

　　给一张无向图，求定向后所成DAG的最长路的最小值。

　　因为点数比较少，考虑状态压缩DP。

　　根据 Dilworth 定理,有向无环图的最长链长度,等于最少反链划分数量。所以问题等价于,把点集分成若干集合,使得每个子集内部没有边。转化后的问题可以用状态压缩动态规划解决,预处理出ok[code]表示集合code内部是否有边,然后计算f[code]表示把集合code划分的最少子集数量,转移的时候枚举subcode满足ok[subcode]为真,用f[code-subcode]+1更新答案。总的时间复杂度是 O(2ⁿm+3ⁿ)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=15,maxc=26;
bool ok[1<<maxn];
int n,m,idx[maxc],g[maxn][maxn],f[1<<maxn];
void init(){
    scanf("%d",&m);
    memset(idx,-1,sizeof(idx));
    for (int i=1;i<=m;++i){
        char s1[2],s2[2];
        scanf("%s%s",s1,s2);
        if (idx[s1[0]-'A']==-1) idx[s1[0]-'A']=n++;
        if (idx[s2[0]-'A']==-1) idx[s2[0]-'A']=n++;
        g[idx[s1[0]-'A']][idx[s2[0]-'A']]=g[idx[s2[0]-'A']][idx[s1[0]-'A']]=1;
    }
}
void work(){
    for (int i=0;i<1<<n;++i){
        ok[i]=1;
        for (int j=0;j<n;++j)
            for (int k=0;k<n;++k)
                if (j!=k&&((i>>j)&1)&&((i>>k)&1)&&g[j][k]){ok[i]=0;break;}
    }
    memset(f,63,sizeof(f));f[0]=0;
    for (int i=0;i<1<<n;++i)
        for (int t=i;t;t=(t-1)&i)
            if (ok[t]) f[i]=min(f[i],f[i^t]+1);
    printf("%d
",f[(1<<n)-1]-2);
}
int main(){
    init();
    work();
    return 0;
}