自动搬运

查看原文

来自洛谷，原作者为

	BJpers2 **

搬运于2025-08-24 21:49:07，当前版本为作者最后更新于2018-10-19 14:51:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题目自从改了空间限制以后就没几个人自己写程序过掉的，最近AC也几乎都是抄的POI的官方题解。就连两位楼主的代码在新的空间（64MB）之下也是无法通过的。

根据传统状压DP,多数人都选择用一个数组直接记录所有状态下的最优解。但无论怎么压缩都是不会低于$1048576 \times 20 \times 4B=80MB$，一定是会爆空间的。

于是有很多人觉得此题不可做，或者就指责管理员。管理员依照原题设定空间限制可以理解，但也没有给出不爆空间就AC的解决方案。

实际上这个问题是有解决方案的，而且这个方案不需要什么奇技淫巧，用一个$01$背包中常用的技巧就够了。这也是几乎所有DP中惯用的节省空间的技巧。

滚动数组。

滚动数组应用的条件是DP阶段之间之间存在拓扑序。更直白地说就是$DAG$上分层。 所有转移只从上一层转移到下一层，不会跨层转移，也不会层内转移。

放到原问题中，这个性质显然是满足的，假如$k$的二进制中有$x$个$1$,那$f[u][k]$能转移到的所有状态$f[v][k']$中,$k'$的二进制内一定有且仅有$x+1$个$1$。

那么我们对所有的二进制数做$1$的数量的分组，二进制中含相同数目$1$的分到同一组。然后每次从上一组转移到下一组。接着就是滚动数组的套路，把上一层腾出来更新更下面一组即可。可以数学的算出一组中的二进制数个数最大为$$C_{20}^{10} =184756$$

这样我们只要开$f[maxK][C_{20}^{10}][2]$的数组就够了。 它的大小是$20 \times 184756 \times 2 \times 4B < 30MB$这样就可以通过 了。

#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
#define pr make_pair
#define fr first
#define sc second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(u) for(int i=hd[u],v=e[i].v,w=e[i].w;i;i=e[i].n,v=e[i].v,w=e[i].w)
#define REQ(u) for(int i=Hd[u],v=E[i].v,w=E[i].w;i;i=E[i].n,v=E[i].v,w=E[i].w)
using namespace std;
typedef long long ll;
typedef pair<int,int> p;
const int N=50050,M=1050000,INF=1000010000,TK=23,S=190000;
struct edge{int n,v,w;}e[M],E[M];
int n,m,K,u,v,w,fl,Fl,to[TK],id[M];
int fa[N],hd[N],Hd[N],g[N],d[TK][N],f[TK][S][2],ans=INF;
set< p >h;
queue< p >q;
void add(int u,int v,int w){e[++fl]=(edge){hd[u],v,w};hd[u]=fl;}
void Add(int u,int v,int w){E[++Fl]=(edge){Hd[u],v,w};Hd[u]=Fl;}
void dijkstra(int x){
	FOR(i,1,n) d[x][i]=INF;
	d[x][x]=0;
	h.insert(p(0,x));
	while(h.size()){
		u=h.begin()->second;h.erase(h.begin());
		REP(u)if(d[x][u]+w<d[x][v]){
			if(d[x][v]<INF) h.erase(p(d[x][v],v));
			d[x][v]=d[x][u]+w;
			h.insert(p(d[x][v],v));
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&K);K++;
	FOR(i,1,m) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	scanf("%d",&m);
	FOR(i,1,m) scanf("%d%d",&u,&v),g[v]|=(1<<u-2);
	FOR(i,1,K) dijkstra(i);
	FOR(i,2,K) g[i]|=(1<<i-2);
	if(K==1) {printf("%d",d[1][n]);return 0;}
	FOR(k,1,(1<<K-1)-1){int cn,tm;for(cn=0,tm=k;tm;tm-=(tm&-tm),cn++);Add(cn,k,0);id[k]=++to[cn];}
	FOR(j,1,K-1)REQ(j){
		FOR(u,2,K) f[u][id[v]][j&1]=INF;
		FOR(u,2,K)if((g[u]|v)==v){
			if(v-(v&-v)>0){
				FOR(x,2,K)if((1<<x-2&v) && x!=u)
					f[u][id[v]][j&1]=min(f[u][id[v]][j&1],f[x][id[v^(1<<u-2)]][j&1^1]+d[x][u]);
			}
			else f[u][id[v]][j&1]=d[1][u];
			if(v==(1<<K-1)-1) ans=min(ans,f[u][id[v]][j&1]+d[u][n]);
		}
	}
	printf("%d",ans);
}/*
8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5
*/