12.[POI2007]ATR-Tourist Attractions

阅读数: 次 2020-11-22

字数：1.6k字 | 预计阅读时长：7分钟

作者：H_D_NULL

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

题意

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

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

每个限制条件形如 $r_i$，$s_i$，表示停留在 $s_i$ 之前必须先在 $r_i$ 停留过。

思路

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

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

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

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

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

舍去冗余状态

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

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

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

细节

需要按顺序遍历点，具体操作为预处理出走到每个点之前需要遍历的点集，和状态转移时的点集进行位运算（乱搞）判断即可；
如果 $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=q.top().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); //因为刚刚没处理1
		printf("%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;
}

本文作者： 益题 Yitee
发布时间： 2020-11-22
最后更新： 2021-08-19
本文标题： 12.[POI2007]ATR-Tourist Attractions
本文链接： https://yitee.top/posts/48870.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！