Loading... ### 状态压缩DP <!--more--> #### 最短哈密顿回路问题 * 给定一个完全图，带正边权$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  \- 设计状态： $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 15, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏