【线上训练 15】生成树
(http://zhengruioi.com/contest/440/problem/1146)
给一个带权完全图，定义一颗生成树 \(T\) 的代价为 \(W(T)=\sum_{1\leq u<v\leq n} dis(u,v)\)。求 \(min W(T)\)。
\(n\leq 15\)
sol：
首先有一种直观的想法，就是先选一个根，然后再往上插一堆子树。考虑 \(DP\)，\(f_{i,u}\) 表示现在选取的点集为 \(i\)，且这棵子树以 \(u\) 为根的最小代价。转移时，我们考虑枚举一个 \(T ⊆ S\) 以及 \(v ∈ T\)，考虑将以 \(v\) 作为根的 \(T\) 中的点拼在 \(u\) 的下面，因此有 \(f_{S,u} = f_{T,v} + f_{S/T,u} + w_{u,v} \times |T| \times (n − |T|)\)。这是 \(O(3^n\times n^2)\) 的，可能过不了，所以再考虑优化。注意到 \(f_{T ,v} + w_{u,v} \times |T| \times (n − |T|)\) 的值只与 \(T, u, v\) 有关，因此我们可以在处理完一个 \(T\) 后顺带求一下 \(min_{v∈T} f_{T ,v} + w_{u,v} \times |T| \times (n − |T|)\)，它的复杂度是 \(O(2^n\times n^2) 的\)。这样的话转移可以少枚举一维 \(v\)，总复杂度\(O(3^n\times n+2^n\times n^2)\)。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x;
}
const int N=16;
int n,edge[N][N],maxn,siz[35000];
ll f[35000][N],g[35000][N],ans=1e17;
int main(){
n=read();maxn=(1<<n)-1;
for(int i=0;i<n;i++) for(int j=1;i+j<n;j++){
int x=read();
edge[i][i+j]=edge[i+j][i]=x;
}
for(int i=1;i<=maxn;i++) siz[i]=siz[i>>1]+(i&1);
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
for(int i=0;i<n;i++) f[1<<i][i]=0;
for(int i=1;i<=maxn;i++){
if(siz[i]!=1){
for(int u=0;u<n;u++){
if(!(i&(1<<u))) continue;
int tmp=i^(1<<u);
for(int j=tmp;1;j=(j-1)&tmp){
f[i][u]=min(f[i][u],f[j|(1<<u)][u]+g[tmp^j][u]);
if(!j) break;
}
}
}
for(int u=0;u<n;u++){
if(i&(1<<u)) continue;
for(int v=0;v<n;v++){
if(!(i&(1<<v))) continue;
g[i][u]=min(g[i][u],f[i][v]+1ll*edge[u][v]*siz[i]*(n-siz[i]));
}
}
}
for(int u=0;u<n;u++) ans=min(ans,f[maxn][u]);
printf("%lld\n",ans);
return 0;
} 【普转提七联测 Day 3】DAG
(http://zhengruioi.com/contest/409/problem/1007)
给出一个 \(n\) 个点 \(m\) 条边无向图，请你给边定向成为一个有向无环图（\(DAG\)），使得最长路最短，求长度。这里的最长路指经过的边的数量。
\(1\leq n\leq 17,1\leq m\leq 136\)
sol：
首先根据经验会发现答案就等于最小染色数或最小独立集覆盖(一个经典的NP问题) \(-1\)。考虑用状压DP求解这个东西。首先 \(O(2^n\times n^2)\) 预处理出图中所有独立集，设 \(f_S\) 表示点集为 \(S\) 时的最小独立集覆盖。枚举子集转移，复杂度 \(O(3^n)\)。
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x;
}
int n,m,maxn,f[150000];
bool p[20][20],ch[20];
int main(){
n=read();m=read();maxn=1<<n;
for(int i=1;i<=m;i++){
int x=read(),y=read();
p[x][y]=p[y][x]=1;
}
memset(f,0x3f,sizeof(f));f[0]=0;
for(int t=1;t<maxn;t++){
bool im=1;
for(int i=t,j=1;j<=n;i>>=1,j++)
if(i&1) ch[j]=1; else ch[j]=0;
for(int i=1;i<=n;i++){
if(!ch[i]) continue;
for(int j=1;j<=n;j++)
if(ch[j]&&p[i][j]){im=0;break;}
if(!im) break;
}
if(im) f[t]=1;
}
for(int t=1;t<maxn;t++)
for(int i=t;i;i=(i-1)&t)
if(f[i]==1) f[t]=min(f[t],f[i^t]+1);
printf("%d\n",f[maxn-1]-1);
return 0;
}