/ Vijos / 题库 / 宝藏 /

题解

2 条题解

  • 3
    @ 2018-03-12 22:11:21

    第一次递交55,明天AC了来补全代码。

    2018.3.13更:今天发现昨天的思路是错的,重新写一遍思路。引用的这一段是错的。

    先讲思路。

    一看数据范围,就知道肯定是 状压DP 。再看到题目中说每个点联通一遍,就知道肯定是 状压集合DP

    马上想到集合DP经典模型: TSP问题

    TSP状态转移方程式如下

    dp[i][v] = min(dp[i][v], dp[(i&(~(1 << v)))][u]+adjm[u][v]);
    

    可是这道题与TSP又有不同:TSP的点一个一个选进集合,构成了一条路径,可是这里需要的是一颗树。路径和树的最大区别是 路径添加点时只能在已有边界点添加,然而树却可以在任意点添加点并形成树枝 ,因此状态转移方程式如下

    dp[i][v][nth+1] = min(dp[i][v][nth+1], dp[(i&(~(1 << v)))][u][nth]+adjm[u][v]*nth);
    dp[i][u][nth] = min(dp[i][u][nth], dp[(i&(~(1 << v)))][u][nth]+adjm[u][v]*nth);
    

    初始化 dp[1 << stp][stp][1] = 0; 遍历 dp[(1<<n)-1] 的后两个状态 [v][nth] 即可得到答案。

    以下开始正确思路

    这个问题和TSP问题的不同之处不仅是点添加的位置,因为是树的生成, 这里的集合可以从两个集合合并而来,因此像TSP一个一个选点进集合会漏解!

    数据卡的不是特别紧,用昨天的错误思路居然可以得50分!

    状态转移方程式

    dp[i][u][nth] = min(dp[i][u][nth], dp[inj][u][nth]+dp[j][v][nth+1]+adjm[u][v]*nth);
    dp[i][v][nth] = min(dp[i][v][nth], dp[inj][u][nth+1]+dp[j][v][nth]+adjm[u][v]*nth);
    

    完整代码

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    const int MAXN = 13;
    const int MAXTWON = 1 << 13;
    const int INF = 0x3f3f3f3f;
    int n, m;
    int adjm[MAXN][MAXN];
    int dp[MAXTWON][MAXN][MAXN]; // dp[BITSET][FROM][NTHNODE]
    int gans = INF;
    
    int main(){
      // freopen("2032.txt", "r", stdin);
      // freopen("2032_out.txt", "w", stdout);
      memset(adjm, 0x3f, sizeof(adjm));
      memset(dp, 0x3f, sizeof(dp));
      scanf("%d %d", &n, &m);
      if(m == 0){
        cout << 0;
        return 0;
      }
      for(int i=0; i<m; i++){
        int tfrom, tto, tl;
        scanf("%d %d %d", &tfrom, &tto, &tl);
        --tfrom;
        --tto;
        adjm[tfrom][tto] = adjm[tto][tfrom] = min(adjm[tfrom][tto], tl);
      }
      for(int j=1; j<n; j++){
        dp[0][0][j] = 0;
        for(int i=0; i<n; i++){
          dp[(1<<i)][i][j] = 0;
        }
      }
      for(int i=1; i<(1<<n); i++){
        for(int j=1; j<(1<<n); j++){
          if((i|j)!=i) continue;
          int inj = i^(i&j);
          // cout << j << " & " << inj << " -> " << i << endl;
          for(int u=0; u<n; u++){
            if(((inj>>u)&1) == 0) continue;
            for(int v=0; v<n; v++){
              if(((j>>v)&1) == 0) continue;
              if(u == v || adjm[u][v] >= INF) continue;
              //merge sets
              for(int nth=1; nth<n; nth++){
                dp[i][u][nth] = min(dp[i][u][nth], dp[inj][u][nth]+dp[j][v][nth+1]+adjm[u][v]*nth);
                dp[i][v][nth] = min(dp[i][v][nth], dp[inj][u][nth+1]+dp[j][v][nth]+adjm[u][v]*nth);
              }
            }
          }
        }
      }
      for(int i=0; i<n; i++){
        gans = min(gans, dp[(1<<n)-1][i][1]);
      }
      cout << gans;
    
      return 0;
    }
    
    

    评测情况

     Accepted
    #   状态  耗时  内存占用
    #1   Accepted   4ms 5.5 MiB
    #2   Accepted   8ms 5.5 MiB
    #3   Accepted   4ms 5.582 MiB
    #4   Accepted   8ms 5.625 MiB
    #5   Accepted   7ms 5.57 MiB
    #6   Accepted   5ms 5.5 MiB
    #7   Accepted   7ms 5.578 MiB
    #8   Accepted   5ms 5.5 MiB
    #9   Accepted   3ms 5.598 MiB
    #10  Accepted   6ms 5.5 MiB
    #11  Accepted   3ms 5.59 MiB
    #12  Accepted   5ms 5.613 MiB
    #13  Accepted   6ms 5.5 MiB
    #14  Accepted   8ms 5.5 MiB
    #15  Accepted   105ms   5.594 MiB
    #16  Accepted   109ms   5.598 MiB
    #17  Accepted   383ms   5.609 MiB
    #18  Accepted   463ms   5.602 MiB
    #19  Accepted   395ms   5.695 MiB
    #20  Accepted   444ms   5.605 MiB
    

    PS:看了luogu题解区,神牛们说这种状压DP貌似还没有暴搜+剪枝快

  • 0
    @ 2023-12-04 13:35:50
    #include<bits/stdc++.h>
    #define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
    #define fr(i,a,b,k) for(int i=a;i!=b;i+=k)// a<b a>b
    using namespace std;
    const int N=1<<13;
    const int inf=0x3f3f3f3f;
    int n,m,x,y,z,co[N>>8][N>>8],f[N][13],a[N][N];
    inline int lowbit(int x)
    {
        return x&(-x);
    }
    signed main()
    {
        IOS;
        cin>>n>>m;
            memset(co,inf,sizeof co);
        fr(i,1,n+1,1)
            co[i][i]=0;
        fr(i,1,m+1,1)
            cin>>x>>y>>z,co[x][y]=co[y][x]=min(co[x][y],z);
        fr(i,0,1<<n,1)
        {
            for(int j=i;j;j=(j-1)&i)
            {
                bool ok=0;
                fr(k,1,n+1,1)
                    if((!((j>>(k-1))&1))&&((i>>(k-1))&1))
                    {
                        int min1=inf;
                        fr(l,1,n+1,1)
                            if(((j>>(l-1))&1))
                                min1=min(min1,co[l][k]);
                        if(min1!=inf)
                            a[j][i]+=min1;
                        else
                            ok=1;
                    }
                if(ok)
                    a[j][i]=0;
            }
        }
        memset(f,inf,sizeof f);
        fr(i,1,n+1,1)
            f[1<<(i-1)][1]=0;
        fr(i,1,1<<n,1)
            fr(j,2,n+1,1)
                for(int k=i;k;k=(k-1)&i)
                    if(a[k][i]&&f[k][j-1]!=inf)
                        f[i][j]=min(f[i][j],f[k][j-1]+(j-1)*a[k][i]);
        int ans=inf;
        fr(i,1,n+1,1)
            ans=min(ans,f[(1<<n)-1][i]);
        cout<<ans; 
        return 0;
    }
    /*
    4 5 
    1 2 1 
    1 3 3 
    1 4 1 
    2 3 4 
    3 4 1 
    */
    
  • 1

信息

ID
2032
难度
6
分类
(无)
标签
递交数
252
已通过
73
通过率
29%
被复制
11
上传者