/ Vijos / 题库 / 宝藏 /

题解

2 条题解

  • 3
    @ 7 年前

    第一次递交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]);
    Copy

    可是这道题与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);
    Copy

    初始化 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);
    Copy

    完整代码

    #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;
}
    Copy

    评测情况

     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
    Copy

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

  • 0
    @ 1 年前 
    #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 
*/
    Copy
  • 1

宝藏

信息

ID
2032
难度
6
分类
(无)
标签
递交数
252
已通过
73
通过率
29%
被复制
11
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1