题解 P3451 【[POI2007]ATR-Tourist Attractions】

· · 题解

这道题目自从改了空间限制以后就没几个人自己写程序过掉的，最近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
*/