为啥我去年这么菜啊。。。。。
我现在想了$20min$后打了$10min$就过了$qwq$。
我们用$f[i][j]$表示当前深度为$i$，访问了状态$j$中的所有点的最小代价。
显然$f[i][j]=min(f[i-1][k]+i\times get(k,j^k)) $其中$k$为$j$的子集，$get(x,y)$表示点集$y$中所有点分别向点集$x$连边的最小代价。
显然这个dp的时间复杂度是$O(3^n\times n^2)$的。
考虑到n非常小，然后就过了。
然而我当年不会枚举子集，甚至单独开了一维来存储深度为i的点集 $555^{555}$
现在写的这份代码比场上那个70分不知道短到哪里去了
1 #include<bits/stdc++.h> 2 #define INF 19260817 3 #define M 12 4 #define lowbit(x) (x&(-x)) 5 using namespace std; 6 7 int a[M][M]={0},f[M][1<<M]={0}; 8 int p[1<<M]={0}; 9 int get(int x,int y){ 10 int res=0; 11 for(int i=y;i;i-=lowbit(i)){ 12 int now=p[lowbit(i)],minn=f[0][0]; 13 for(int j=x;j;j-=lowbit(j)){ 14 int pre=p[lowbit(j)]; 15 minn=min(minn,a[now][pre]); 16 } 17 res+=minn; 18 } 19 return res; 20 } 21 22 int main(){ 23 for(int i=0;i<M;i++) p[1<<i]=i; 24 memset(a,1,sizeof(a)); 25 memset(f,1,sizeof(f)); 26 int n,m; 27 scanf("%d%d",&n,&m); 28 for(int i=1;i<=m;i++){ 29 int x,y,z; scanf("%d%d%d",&x,&y,&z); 30 x--; y--; 31 a[x][y]=min(a[x][y],z); 32 a[y][x]=min(a[y][x],z); 33 } 34 int ans=f[0][0],hh=1<<n; 35 if(n==1) ans=0; 36 for(int i=0;i<n;i++) f[0][1<<i]=0; 37 for(int i=1;i<n;i++){ 38 for(int j=1;j<hh;j++){ 39 for(int k=j;k;k=j&(k-1)) 40 f[i][j]=min(f[i][j],f[i-1][k]+get(k,j^k)*i); 41 } 42 ans=min(ans,f[i][hh-1]); 43 } 44 cout<<ans<<endl; 45 }
转播
