状态压缩DP

最短哈密顿回路问题

  • 给定一个完全图,带正边权$w(u,v)$。求出一个顶点的排列$v\_1,v\_2,...,v\_n$,使得$w(v\_1,v\_2),w(v\_2,v\_3),...,w(v\_{n-1},v\_n),w(v\_n,v_1)$的和最小。
  • $n\\leq17$
  • $f\[i\]\[j\]$表示在$i$这个点集中,从$0$到$j$的最短距离。($0和$j$都在$i$集合里)//0~n-1

    for(int i=0;i<n;i++) for(int j=0;j<n;j++) f[i][j]=inf;
    f[1<<0][0]=0;
    for(int i=1;i<(1<<n);i++){
        if(!(i&1)) continue;
        for(int j=0;j<n;j++){
            if(!((1<<j)&1)) continue;
            for(int k=1;k<n;k++){
                if((1<<k)&i) continue;
                f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+w[j][k]);
            }
        }
    }
    
    int ans=inf;
    for(int j=1;j<n;j++){
        ans=min(ans,f[(1<<n)-1][j]+w[j][0]);
    }

例题2

例题2 - 设计状态: $f\[i\]\[S\]$表示只填入前i行当每个格子,有多少种合法方案,使得第$i$行当01串等于$S$。(合法:相邻两个格子不同时为$1$)。 ```cpp sum=0; for(int i=0;i<(i<<n);i++){ sum=sum+f[n][i]%p; }

bool xl[1<<10];
for(int i=0;i<(1<<10);i++)
    if("S串中存在两个相邻的1"){
        xl[S]=1;
    }
for(int s=0;s<(1<<m);s++)
    f[1][s]=!xl[s];

for(int i=2;i<n;i++){
    for(int =0;s<(1<<m);s++){
        if(xl[s]) f[i][s]=0;
        else{
            //假设上一行填的是t
            for(int t=0;t<(1<<m);t++){
                if((t&s)==0) f[i][s]=(f[i][s]+f[i-1][t])%p;
            } 
        }
    }
}
```
</code></pre>

- 优化后
    ```cpp
    sum=0;
    for(int i=0;i<(i<<n);i++){
        sum=sum+f[n][i]%p;
    }

bool xl[1<<10];
for(int i=0;i<(1<<10);i++)
    if("S串中存在两个相邻的1"){
        xl[S]=1;
    }
for(int s=0;s<(1<<m);s++)
    f[1][s]=!xl[s];

for(int i=2;i<n;i++){
    for(int =0;s<(1<<m);s++){
        if(xl[s]) f[i][s]=0;
        else{
            int buji=(1<<m)-1-s;//补集 
            for(int t=buji;t;t=(t-1)&buji){
                f[i][s]=(f[i][s]+f[i-1][t])%p;
            }
            f[i][s]=(f[i][s]+f[i-1][0])%p;
        }
    }
}
```


Dominating set支配集

​ 一个无向图的支配集是一个点的子集$S$,使得图中每个点都属于S或者与至少与一个$S$中的节点相邻 二者至少一个成立 $n$个点的二分图,求其最小支配集。$n\leq30$(两边一共$n$个点)

Last modification:March 15th, 2020 at 09:04 pm