2 条题解
-
3zyc2000 LV 9 @ 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貌似还没有暴搜+剪枝快
-
02023-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
- 分类
- (无)
- 标签
- 递交数
- 251
- 已通过
- 72
- 通过率
- 29%
- 被复制
- 11
- 上传者