题目大意不说了,可以自己去看
点我跳转 (゚▽゚*)
首先这是noip考试,考场上我们要先写暴力,不仅能对拍,还能骗分。
一个显然的想法就是枚举全排列,然后暴力。
哇!70分。
传说去年报送学长一年没摸键盘敲了个枚举生成树暴力骗了90?忘了。
先不说这些废话,在我们有70分保底时,我们该去想正解了。
你发现数据范围很小,我们可以用什么状压dp?
考虑设计状态,我们肯定有一维是状态j,表示已经开发了点集为j时的最小开销,
显然不能转移,考虑加维。
考虑我们转移时还需要什么。
看题目里给的公式:\mathrm{L} \times \mathrm{K}
l是已知的,k不一定啊?
k是什么,经过点的个数?这个图是个树?
那k不就是深度?
深度最多是n?
考虑可以逐层转移。
dp[i][j]表示现在转移到第k层,开发了点的集合是j时的最小方案。
显然我们转移需要枚举在这层加入的点集。
大概就是j的补集的子集。
总复杂度和枚举子集的子集一样。
(格罗姆:那么,古尔丹,代价是什么呢?)
代价?对了,还有转移的代价如何计算?
显然我们当时读入时先存下一个最优邻接表。
然后对于一个数枚举和那个点连边即可。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF=7e7+5;
const int N=(1<<12)+5;
int n,m;
int mmp[15][15];
int dp[15][N],pos[N],val[15],nmb[15],res[N],tmd[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i) for(int j=0;j<n;++j) mmp[i][j]=INF;
for(int i=1,x,y,z;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);x--;y--;
mmp[x][y]=min(mmp[x][y],z);
mmp[y][x]=mmp[x][y];
}
// for(int i=0;i<n;++i) {for(int j=0;j<n;++j) printf("%d ",mmp[i][j]);printf("\n");}
for(int i=0;i<n;++i) pos[1<<i]=i;//pos表示二进制数所代表的节点
memset(dp,0x3f3f3f3f,sizeof dp);
for(int i=0;i<n;++i) dp[0][1<<i]=0;
for(int i=0;i<n;++i)
{
for(int st=0;st<(1<<n);++st)
{
int tot=0;
for(int k=0;k<n;++k)
{
if(st&(1<<k)) continue;
val[tot]=INF;nmb[tot]=1<<k;
for(int j=st;j;j-=j&-j)
val[tot]=min(val[tot],mmp[k][pos[j&-j]]*(i+1));
tot++;
}
for(int j=1;j<(1<<tot);++j)
{
res[j]=res[j-(j&-j)]+val[pos[j&-j]];
tmd[j]=tmd[j-(j&-j)]|nmb[pos[j&-j]];
dp[i+1][st|tmd[j]]=min(dp[i+1][st|tmd[j]],dp[i][st]+res[j]);
}
}
}
int ans=INF;
for(int i=0;i<=n;++i) ans=min(ans,dp[i][(1<<n)-1]);
printf("%d\n",ans);
}