12.[POI2007]ATR

12.[POI2007]ATR

date: 2020-11-22 20:44
title: ‘12.[POI2007]ATR-Tourist Attractions’
tags:

• 进阶
• 提高
• 动态规划

作者：H_D_NULL

题目链接：P3451 [POI2007]ATR-Tourist Attractions

题意

给出一张有 n n n 个点 m m m 条边的无向图，每条边有边权。

你需要找一条从 1 1 1 到 n n n 的最短路径，并且这条路径在满足给出的 g g g 个限制的情况下可以在所有编号从 2 2 2 到 k + 1 k+1 k+1 的点上停留过。

每个限制条件形如 r i r_i ri​， s i s_i si​，表示停留在 s i s_i si​ 之前必须先在 r i r_i ri​ 停留过。

思路

注：如果连这道题暴力状压的写法都不会，推荐先去康题解区的“错误”代码（大雾）

…写完状压以后自然是传统 OI 点到为止，保留 SPFA 把 Dij 注释掉，我笑一下决定 AC ，因为这时间，按照传统 OI 电刀喂纸他已经输了。如果用 Dij ，再强的数据也卡不掉我的时间了…我提交不优化了，他突然袭击，来卡我空间，啊，我大意了啊，没有卡空间…♂啊，看来是，有 bear 而来！

K m a x = 20 K_{max}=20 Kmax​=20 ，状压无疑，预处理出要经过的城市的单源最短路（类似一道叫新年好的题）；

按照传统的状压 DP ，状态应设为 f [ k ] [ S ] f[k][S] f[k][S] ：遍历集合为 S S S 的点后（以下简称点集），停在 k k k 点所走的最短路程，因为起始城市必为 1，终止城市为 n，故这两个点不计入状态，统计答案时特别处理即可；

但是我们发现即便如此，空间也会炸（其他题解说得很清楚了），所以考虑优化；

舍去冗余状态

要优化空间，最好的方式即是舍去冗余状态，比如滚动数组，但是一般的状压 DP 线性枚举点集，而状态并不线性转移，故无法直接滚动；

我们分析一下本题状态转移的实质以便优化。枚举到任意点集时，我们从中继续枚举出一点，然后用剩余点组成的点集的答案来优化本点集的答案。不难发现，如此转移状态，点集中点的数量，即这个数二进制下一的个数，是递增的，且固定+1，故可以用滚动数组优化；

按照传统状压 DP 无法使用滚动数组的原因是，通过线性枚举的点集，无法保证二进制下一的数量呈单增。为解决这个问题，只需要预处理出符合每个点集数目 n u m num num（ n u m ∈ ( 0 , k ] num in (0,k] num∈(0,k]）的所有点集即可。对于任一 n u m num num ，其包含的点集数为 C n k C{n atop k} Ckn​，最多为 C 10 20 = 184756 C{10 atop 20}=184756 C2010​=184756，空间完全可以承受；

细节

• 需要按顺序遍历点，具体操作为预处理出走到每个点之前需要遍历的点集，和状态转移时的点集进行位运算（乱搞）判断即可；

• 如果 k = 1 k=1 k=1，直接输出起点到终点的最短路；

• 注意写一般状压的时候不要用这个套路，因为本做法本质上是牺牲时间来优化空间；

• 尽量不要用已死的算法（逃

这个出题人不讲武德，来，骗！来，卡常！我六十九岁的老OIer。这好吗？这不好！我劝，这位出题人耗子尾汁，好好反思，以后不要再犯这样的聪明，小聪明，♂啊…OI要以和为贵，要讲污的，不要搞窝里斗，谢谢朋友们！

Talk is cheap, show me the code

#include<bits/stdc++.h>
#define re register
using namespace std;const int K=22;
const int N=20005;
const int M=200005;inline int read(){re int ret=0;re char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9'){ret=(ret<<1)+(ret<<3)+(c^48);c=getchar();} return ret;
}int n,m,k;struct Edge{int nxt;int to;int v;
} e[M<<1];int h[N],cnt;inline void Add(int x,int y,int v){e[++cnt].nxt=h[x];e[cnt].to=y;e[cnt].v=v;h[x]=cnt;
}int cond[K];
int dis[K][N];bool vis[N];#define MK(x,y) make_pair((x),(y))inline void DIJ(int st) {memset(vis,0,sizeof(vis));memset(dis[st],63,sizeof(dis[st]));priority_queue < pair<int,int> > q;dis[st][st]=0; q.push(MK(0,st));while(!q.empty()){re int l&#p().second; q.pop();if(vis[l]) continue; vis[l]=1;for(re int i=h[l],to,v;i;i=e[i].nxt){to=e[i].to;v=e[i].v;if (dis[st][l]+v<dis[st][to]){dis[st][to]=dis[st][l]+v;q.push(MK(-dis[st][to],to));}}}
}inline void Init(){n=read(); m=read(); k=read()+1;for(re int i=1,x,y,v;i<=m;i++){x=read(); y=read(); v=read();Add(x,y,v); Add(y,x,v);} re int T=read();for(re int i=1,x,y;i<=T;i++){x=read(); y=read();cond[y]|=(1<<(x-2)); //处理到达之前需要遍历的点集}for(re int i=2;i<=k;i++) DIJ(i); //为了省时间，1和n不必处理
}struct K{int nxt;int to;
} R[1<<21];int h_R[K],cnt_R;
int sum[K],bl[1<<21];
int f[2][K][184760];inline void Add_K(int x,int y){R[++cnt_R].nxt=h_R[x];R[cnt_R].to=y;h_R[x]=cnt_R;
}#define lowbit(x) ((x)&(-(x)))
#define For(p) for(re int rg=h_R[(p)],to=R[rg].to;rg;rg=R[rg].nxt,to=R[rg].to)
//遍历点个数为p的点集的集合（绕）inline void Solve(){if(k==1){DIJ(1); //因为刚刚没处理1printf("%d",dis[1][n]);return;}for(re int i=1,num,now;i<1<<(k-1);i++){for(num=0,now=i;now;now-=lowbit(now),num++); //求"1"的个数Add_K(num,i); bl[i]=++sum[num];//处理编号}For(1){for(re int i=2;i<=k;i++){if(to&(1<<(i-2))){f[0][i][bl[to]]=dis[i][1]; //从1出发到此的距离break;}}}re int l=1,ans=1<<30;for(re int NUM=2;NUM<k;NUM++,l^=1){For(NUM){for(re int i=2,now;i<=k;i++){if((to&(1<<(i-2)))&&((cond[i]&to)==cond[i])){now=to^(1<<(i-2));  f[l][i][bl[to]]=1<<30;for(re int j=2;j<=k;j++){if((now&(1<<(j-2)))&&((cond[j]&now)==cond[j])){if(f[l][i][bl[to]]>f[l^1][j][bl[now]]+dis[i][j]){f[l][i][bl[to]]=f[l^1][j][bl[now]]+dis[i][j];}}}}}}}For(k-1){for(re int i=2;i<=k;i++){if((to&(1<<(i-2)))&&((cond[i]&to)==cond[i])){ans=min(ans,f[l^1][i][bl[to]]+dis[i][n]);//加上从这个点到n的距离}}}printf("%d",ans);
}int main(){Init(); Solve();return 0;
}

本文链接： 12.[POI2007]ATR-Tourist Attractions