CF793D Presents in Bankopolis/Namomo Spring Camp 每日一题 Week 1Day2 No Crossing

一个有 n n n个点 m m m条边的有向图, 你需要找到恰好经过 k k k个点的最短路径, 要求每次选的边不能越过之前已经经过的节点. 即对于路径中 x → y xto y x→y. 不存在以前经过的点 t t t使得三者编号满足 min ⁡ ( x , y ) ≤ t ≤ max ⁡ ( x , y ) min(x,y)leq tleq max(x,y) min(x,y)≤t≤max(x,y).

首先我们考虑选择一条边 x → y xto y x→y. 如果 x < y x y x>y x>y那么后续选择路径的时候不能经过点 k k k满足 k > x k>x k>x的点.

如果我们直接建图, 一开始我们能够经过 n n n上的任意节点, 然后没选择一条边就会减少可以到达的节点数目, 使得可以到达的节点减少, 并且我们可以知道可以到达节点一定是连续的.

如果我们之间进行DP, 我们进行分类讨论来确定可以到达那些节点, 非常地麻烦.

我们考虑反向建边, 我们建立反向边之后. 题意等价于我当前 x → y xto y x→y后 x ≤ k ≤ y xleq kleq y x≤k≤y的点 k k k都是不能够再次达到的. 这样就避免了分类讨论的问题.

我们设 f i , v , l , r f_{i,v,l,r} fi,v,l,r​表示选择 i i i条边, 当前处于 v v v点, 不可以再次到达 [ l , r ] [l,r] [l,r]这个区间内的点的最小花费.

那么我们可以简单得得到一个转移方程: f i + 1 , T o v , min ⁡ { l , T o v } , max ⁡ { r , T o v } = min ⁡ { f i , v , l , r + W v } f_{i+1,To_v,min{l,To_v},max{r,To_v}}=min{f_{i,v,l,r}+W_v} fi+1,Tov​,min{l,Tov​},max{r,Tov​}​=min{fi,v,l,r​+Wv​}.

时间复杂度 O ( 能 过 ) O(能过) O(能过).

优化方式:

为了避免无用的状态, 我们可以用 m a p map map或 u n o r d e r e d _ m a p unordered_map unordered_map直接去维护可以达到的状态.如果我们事先对每一个节点的出边 u u u, 其出边 ( u , v ) (u,v) (u,v)按 v v v排序后. 那么转移时候的可行边一定是一个前缀和一个后缀.如果想用 u n o r d e r e d _ m a p unordered_map unordered_map维护 D P DP DP值需要一个Hash建立一个双射区间 [ l , r ] [l,r] [l,r]映射到一个整数. 这里我们不妨用下列映射 [ l , r ] → l − 1 + r × n [l,r]to l-1+rtimes n [l,r]→l−1+r×n那么 K e y → [ K e y m o d    N + 1 , K e y / N ] Keyto[Keymod N+1,Key/N] Key→[KeymodN+1,Key/N]. Code

# define Fast_IO std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# include "unordered_map"
# include "algorithm"
# include "iostream"
# include "cstdlib"
# include "cstring"
# include "cstdio"
# include "vector"
# include "bitset"
# include "queue"
# include "cmath"
# include "map"
# include "set"

using namespace std;

const int maxm=1e2+10;
const int INF=1<<30;

int N,K,M;
vector > Edge[maxm];
unordered_map DP1[maxm],DP2[maxm];

int Hash(pair Now){
	return Now.first-1+Now.second*N;
}
pair Inv_Hash(int H){
	return {H%N+1,H/N};
}

int main(){
	int i,j,k,A,B,C,L,R,Cost,W,To,Ans;
	pair Interval,Now_Edge;
	scanf("%d%d%d",&N,&K,&M);
	if(K==0 || K==1){
		printf("0");
		return 0;
	}
	for(i=1;i<=M;i++){
		scanf("%d%d%d",&A,&B,&C);
		Edge[B].push_back({A,C});
		DP2[A][Hash({min(A,B),max(A,B)})]=DP2[A][Hash({min(A,B),max(A,B)})]==0?C:min(C,DP2[A][Hash({min(A,B),max(A,B)})]);
	}
	for(i=1;i<=N;i++) sort(Edge[i].begin(),Edge[i].end());
	
//	printf("%d %d",Inv_Hash(Hash({1,2})).first,Inv_Hash(Hash({1,2})).second);
	for(i=1;i=L && To<=R) continue;
					DP2[To][Hash({min(L,To),max(R,To)})]=DP2[To][Hash({min(L,To),max(R,To)})]==0?Cost+W:min(DP2[To][Hash({min(L,To),max(R,To)})],Cost+W);
				}
			}
		}
	}
	Ans=INF;
	for(i=1;i<=N;i++){
		for(auto Now:DP2[i]){
			Ans=min(Ans,Now.second);
		}
	}
	printf("%d",Ans==INF?-1:Ans);
	return 0;
}

link1: Daimayuan online Judge 437.

link2: CF793D Presents in Bankopolis.