分层图思想¶
例题 #1 [CSP-J2019] 加工零件¶
思路
我们该如何解决问题？
问题：a做k阶段的零件b要不要做呢？
其实，实质就是看a到b有没有长度为k的路径。
同时我们会发现，如果a到b有长度为k的路径，那么a到b一定有长度为k+2的路径，但并不一定有长度为k+1的路径。（因为我们可以来回走一条边）
所以，我们要对每个点求一遍奇数路径，和偶数路径（这里求最短路就行）。
/*
CB Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
const int N=2e5+5;
const int INF=1e9+5;
const int MOD=1e9+7;
bool f1;
int dis1[N],dis2[N];
int l[N],r[N];
int q,n,m,ans,T,k;
vector<int>e[N];
bool f2;
#define rd read()
inline int read()
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
void add(int a,int b){
e[a].push_back(b);
e[b].push_back(a);
}
priority_queue<pair<int,int> >pq;
void djstr() {
for(int i=1; i<=n; i++)dis1[i]=INF; //初始化边权
for(int i=1; i<=n; i++)dis2[i]=INF; //初始化边权
for(auto v:e[1]){
dis1[v]=1;
pq.push(make_pair(-1,v));
}
while(pq.size()) { //搜完全图
int u=pq.top().second;
int w=-pq.top().first;
pq.pop();
// if(vis[u])continue;//记得continue
// vis[u]=1;
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(w%2){
if(dis2[v]>1+w){
dis2[v]=w+1; //更新
pq.push(make_pair(-dis2[v],v));
}
}else{
if(dis1[v]>1+w){
dis1[v]=w+1; //更新
pq.push(make_pair(-dis1[v],v));
}
}
}
}
}
signed main(){
n=rd;m=rd;q=rd;
for(int i=1;i<=m;i++){
int u=rd,v=rd;
add(u,v);
}
djstr();
for(int i=1;i<=q;i++){
int a=rd;l[a]=rd;
if(l[a]%2){
if(dis1[a]>l[a])cout<<"No\n";
else cout<<"Yes\n";
}else{
if(dis2[a]>l[a])cout<<"No\n";
else cout<<"Yes\n";
}
}
return 0;
}
例题 #2 [JLOI2011] 飞行路线¶
思路
套路题，分层图。
以样例为例（使用 @EternalAlexander 这位dalao的OI Painter绘制）：
各层内部正常连边，各层之间从上到下连权值为0的边。每向下跑一层，就相当于免费搭一次飞机。跑一遍从\(s\)到\(t+n\times k\)的最短路即可。
引用自SuperJvRuo
我们要考虑枚举每一层的t，因为可能我们用不到k次免费机会。
/*
CB Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int,int>
const int N=5e3+5;
const int INF=1e9+5;
const int MOD=998244353;
bool f1;
struct node{
int nxt,dis;
};
vector<node>e[N];
priority_queue<pair<int,int> >pq;
int n,vis[N],dis[N],m,k,s,t;
bool f2;
#define rd read()
inline int read()
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
void add(int a,int b,int c){
e[a].push_back({b,c});
}
void djstr(int rt) {
pq.push(make_pair(0,rt));
int u=rt; //先从起点开始查
memset(dis,0x3f3f,sizeof dis); //初始化边权
dis[rt]=0;
while(pq.size()) { //搜完全图
u=pq.top().second;
pq.pop();
if(vis[u])continue;//记得continue
vis[u]=1;
for(int i=0;i<e[u].size();i++){
int v=e[u][i].nxt,w=e[u][i].dis;
if(!vis[v]&&dis[u]+w<dis[v]){
dis[v]=dis[u]+w; //更新
pq.push(make_pair(-dis[v],v));
}
}
}
}
signed main(){
// freopen("school.in", "r", stdin);
// freopen("school.out", "w", stdout);
n=rd;m=rd;k=rd;
s=rd;t=rd;
for(int i=1;i<=m;i++){
int a=rd,b=rd,c=rd;
add(a,b,c);
add(b,a,c);
for(int j=1;j<=k;j++){//建k层图
add(a+(j-1)*n,b+(j*n),0);
add(b+(j-1)*n,a+(j)*n,0);
add(a+j*n,b+j*n,c);
add(b+j*n,a+j*n,c);
}
}
djstr(s);
int ans=INF;
for(int i=0;i<=k;i++)ans=min(ans,dis[t+i*n]);
cout<<ans;//dis[t+k*n];
return 0;
}
/*
5 3 3
2 3 4 7 6
*/
练习 #1 [USACO17FEB] Why Did the Cow Cross the Road I G¶
FJ的牧场可以看作是一块 \(N\times N\) 的田地（\(3\le N\le 100\)），\(N-1\) 条南北向的道路和 \(N-1\) 条东西向的道路贯穿整个牧场，同时是每块田野的分界线。牧场的最外面是一圈高大的栅栏以防止奶牛离开牧场。Bessie只要穿过分离两块田野的道路，就可以从任何田野移动到与其相邻的田野里去（北，东，南或西）。当然，Bessie穿过每一条马路都是需要\(T\) 时间的。（\(0\le T\le 1,000,000\)）
有一天，FJ邀请Bessie来他家下棋，Bessie从牧场的西北角出发，FJ的家在牧场的东南角。因为Bessie在中途可能会饿，所以她每走过三块田野就要停下来，享用她所在田野上的新鲜的牧草（不包括Bessie的出发点，但是可能会包括终点FJ的家），牧场上有些田野的牧草长得比其他地方茂盛，所以Bessie对应的停留时间也会变长。
请帮帮Bessie计算出她走到FJ家的最短时间。
也可以使用bfs来做，但是分层图会套路一些。
/* Erica N */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
int xx = 0, ff = 1;char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int a[N];
vector<int> e[N];
int d[N];
int n,t;
priority_queue<pii> pq;
inline int getId(int a,int b){
return n*(a-1)+b;
}
bitset<N> vis;
void djstr(){
memset(d,0x3f3f,sizeof d);
d[1]=0;
pq.push(mp(0,1));
while(pq.size()){
int x=pq.top().ps;
pq.pop();
if(vis[x])continue;
vis[x]=1;
for(auto v:e[x]){
int w=d[x]+t+a[v];
if(!vis[v]&&d[v]>w){
d[v]=w;
pq.push(mp(-d[v],v));
}
}
}
}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void add(int a,int b){
e[a].pb(b);
}
void solve(){
n=rd,t=rd;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[getId(i,j)]=rd;
for(int k=0;k<4;k++){
int x=i+dx[k];
int y=j+dy[k];
if(x<1||x>n||y<1||y>n)continue;
add(getId(i,j),getId(x,y)+n*n);
add(getId(i,j)+n*n,getId(x,y)+n*n+n*n);
add(getId(i,j)+n*n+n*n,getId(x,y));
}
}
}
djstr();
int ans=INF;
for(int i=0;i<3;i++){
ans=min(ans,d[getId(n,n)+n*n*i]);
}
cout<<ans<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}