喜欢的话就坚持吧

10月 26

0.00 avg. rating (0% score) - 0 votes

题目大意不说了,可以自己去看

点我跳转 (゚▽゚*)


首先这是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);
}
0.00 avg. rating (0% score) - 0 votes
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注