P5222 Game

(Updated: )
oi
,

Description

题目链接：P5222

给定一个 $N\times M$ 的网格，其中有 $T$ 个格子有障碍，现需要在第一列摆一定量棋子，每一次可以执行以下操作：

  1. 向上/向下移动一枚棋子一个单位，且该位置没有障碍、没有其他棋子
  2. 将本列所有棋子移动到下一列，且下一列目标位置没有障碍

再给定 $Q$ 个询问，每个询问给出 $k_i$，询问最多能在第一列上放多少棋子，使得经过若干操作后把所有棋子移动到最后一列，且所有棋子加起来总共最多执行 $k_i$ 次 $1$ 操作。

$N\leq 50,M\leq 10^6,T\leq 10^3,Q\leq 10^5$

Solution

首先可以发现 $M$ 肯定是没有任何用的，可以把中间全是没有障碍的列直接缩掉，这样网格就变成了 $N\times T$ 大小。

然后我们还可以对询问进行转化，可以先预处理出一开始摆放 $i(1\leq i \leq N)$ 个棋子在第一列时，最少执行操作 $1$ 的次数，从而在每次询问中做到 $\mathcal O(N)$ 求解答案，那么询问总时间复杂度就是 $\mathcal O(NQ)$ 的。

接下来的问题就是如何预处理摆放 $i$ 个棋子为第一列时，最少执行操作 $1$ 次数。

既有障碍物又不能和另外的棋子重叠，这时我们可以想到可以用费用流解决这道题。

80分做法

可以把每个点向合法的上/下面的相邻的点连一条容量为 $inf$，代价为 $1$ 的边，表示操作 $1$。

每个点再向合法的右边一列连一条容量为 $1$，代价为 $0$ 的边，表示操作 $2$。

但为什么操作 $1$ 要连 $inf$ 呢？

可以参考这种情况：

其中.表示空，方块表示障碍。

显然中间有一条上下的边会走过两次，如果容量为 $1$ 就无法通过。

最后再建立一个超级源点连接第一列所有点，超级汇点连接最后一列所有点，容量均为 $1$，代价均为 $0$，再把超级源点拆成两个点，每次多摆放一个棋子就把这两个点之间的容量 $+1$ 即可。

此时点的总数为 $NT$，边的总数为 $N^2T$。

期望总时间复杂度为 $\mathcal O(N^2TF)$，最坏时间复杂度为 $\mathcal O(N^3T^2F)$（$F$ 表示最大流流量）。

100分做法

由于费用流期望复杂度为 $\mathcal O(MF)$，最坏复杂度为 $\mathcal O(NMF)$，然而这里所有的边的容量均为 $1$，所以可以在这种 $0/1$ 网格图中跑 Spfa 时用双端队列 (deque) 优化 Spfa，每次插入时跟队头比较，如果更小就插入队头，否则插入队尾，然后我不知道这样时间复杂度为多少，反正出题人 CYJian 说是 $\mathcal O(N^3T)$，足以通过此题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e3+10,M=55,R=N*M,E=N*M*M;
int n,m,S,T,TT,Q,cnt,G[M][N],fir[R],nxt[E<<1],son[E<<1],w[E<<1],cost[E<<1],tot=1,Ans,Cost,F[R],C[R],P[R],vis[R],inf=2e9,ans[M];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
PA b[N];
I bool cmp(Cn PA& x,Cn PA& y){return x.se<y.se;}
I void Add(CI x,CI y,CI z,CI c){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,cost[tot]=c;nxt[++tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0,cost[tot]=-c;}
deque<int> q;
#define to son[i]
I bool bfs(){
    RI u,i;W(!q.empty()) q.pop_front();q.push_front(S);memset(C,63,sizeof(C)),memset(vis,0,sizeof(vis));F[S]=inf=C[0];C[S]=0;W(!q.empty())
        for(i=fir[vis[u=q.front()]=0,u],q.pop_front();i;i=nxt[i]) if(w[i]>0&&C[to]>C[u]+cost[i]) C[to]=C[u]+cost[P[to]=i],F[to]=min(F[u],w[i]),!vis[to]&&(q.empty()?q.push_front(to),0:(C[to]>C[q.front()]?q.push_back(to):q.push_front(to),0),vis[to]=1);//Spfa 双端队列优化
    return C[T]<inf;
}
I void MCMF(){
    RI i;W(bfs()){
        for(i=T;i^S;i=son[P[i]^1]) w[P[i]]-=F[T],w[P[i]^1]+=F[T];
        Ans+=F[T];Cost+=F[T]*C[T];
    }return ;
}
#define idx(i,j) (((i)-1)*cnt+j)
int main(){
    RI i,j,x;for(read(n,m,TT,Q),i=1;i<=TT;i++) read(b[i].fi,b[i].se);sort(b+1,b+TT+1,cmp);
    for(i=1;i<=TT;i++) b[i-1].se+2<=b[i].se&&cnt++,b[i-1].se<b[i].se&&cnt++,G[b[i].fi][cnt]=1;//删除空白列
    for(S=n*cnt+1,T=n*cnt+2,i=1;i<=n;i++) for(j=2;j<=cnt;j++) if(!G[i][j-1]&&!G[i][j]) Add(idx(i,j-1),idx(i,j),1,0);//向同行下一列连边
    for(i=1;i<n;i++) for(j=1;j<=cnt;j++) if(!G[i][j]&&!G[i+1][j]) Add(idx(i,j),idx(i+1,j),inf,1),Add(idx(i+1,j),idx(i,j),inf,1);//向同列隔壁行连边
    for(i=1;i<=n;i++) if(!G[i][1]) Add(0,idx(i,1),1,0);//超级源点向第一列连边
    for(i=1;i<=n;i++) if(!G[i][cnt]) Add(idx(i,cnt),T,1,0);//最后一列向超级汇点连边
    for(i=1;i<=n;i++) if(Add(S,0,1,0),MCMF(),Ans==i) ans[i]=Cost;else n=i-1;//每次多加1的容量
    for(i=1;i<=Q;i++){for(read(x),j=n;~j;j--) if(ans[j]<=x) break ;writeln(j);}return 0;
}

想要跑得更快？

陈指导发现这个图其实可以缩点，然后时间复杂度就变成了优秀的 $\mathcal O(NT)$。

首先可以知道如果有 $x$ 个连续的棋子一起向上移动一个单位就等价于把最下面的一个棋子向上移动 $x$ 个单位。

也就是我们可以花费 $i-j$ 的代价把同一列第 $i$ 行棋子移动到第 $j$ 行，但要求 $i$ 到 $j$ 之间没有障碍。

另外还有一个显然的结论就是如果下一个格子没有障碍，我们就不必花费 $1$ 的代价移动这个棋子。

也就是同一行连续一段没有障碍的格子一旦进入了这一段后，必然会一直沿着这条路直到碰到障碍。

那么我们可以把同一行的连续的空格子的点缩成一个点。

这样点数就变成了 $\mathcal O(T)$，边数变成了 $\mathcal O(NT)$，然后就有了十分优秀的复杂度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e3+10,M=55,R=N*M,E=N*M*M;
int n,m,S,T,TT,Q,cnt,G[M][N],fir[R],nxt[E<<1],son[E<<1],w[E<<1],cost[E<<1],tot=1,Ans,Cost,F[R],C[R],P[R],vis[R],inf=2e9,ans[M],ID,id[M][N];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
PA b[N];
I bool cmp(Cn PA& x,Cn PA& y){return x.se<y.se;}
I void Add(CI x,CI y,CI z,CI c){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,cost[tot]=c;nxt[++tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0,cost[tot]=-c;}
deque<int> q;
#define to son[i]
I bool bfs(){
    RI u,i;W(!q.empty()) q.pop_front();q.push_front(S);memset(C,63,sizeof(C)),memset(vis,0,sizeof(vis));F[S]=inf=C[0];C[S]=0;W(!q.empty())
        for(i=fir[vis[u=q.front()]=0,u],q.pop_front();i;i=nxt[i]) if(w[i]>0&&C[to]>C[u]+cost[i]) C[to]=C[u]+cost[P[to]=i],F[to]=min(F[u],w[i]),!vis[to]&&(q.empty()?q.push_front(to),0:(C[to]>C[q.front()]?q.push_back(to):q.push_front(to),0),vis[to]=1);//Spfa 双端队列优化
    return C[T]<inf;
}
I void MCMF(){
    RI i;W(bfs()){
        for(i=T;i^S;i=son[P[i]^1]) w[P[i]]-=F[T],w[P[i]^1]+=F[T];
        Ans+=F[T];Cost+=F[T]*C[T];
    }return ;
}
#define idx(i,j) id[i][j]
int main(){
    RI i,j,k,x;for(read(n,m,TT,Q),i=1;i<=TT;i++) read(b[i].fi,b[i].se);sort(b+1,b+TT+1,cmp);
    for(i=1;i<=TT;i++) b[i-1].se+2<=b[i].se&&cnt++,b[i-1].se<b[i].se&&cnt++,G[b[i].fi][cnt]=1;
    for(i=1;i<=n;i++) for(j=1;j<=cnt;j++) if(!G[i][j]&&!G[i][j-1]&&j>1) id[i][j]=id[i][j-1];else id[i][j]=++ID;//缩点+重新标号
    for(S=++ID,T=++ID,S<<=1,T<<=1,i=1;i<=n;i++) for(j=1;j<cnt;j++){
        k=i-1;W(k>=1&&G[i][j+1]&&!G[i][j]&&!G[k][j]) !G[k][j+1]&&(Add(idx(i,j)<<11,idx(k,j+1)<<1,1,abs(i-k)),0),k--;
        k=i+1;W(k<=n&&G[i][j+1]&&!G[i][j]&&!G[k][j]) !G[k][j+1]&&(Add(idx(i,j)<<11,idx(k,j+1)<<1,1,abs(i-k)),0),k++;//转化：向同列不同行连边
    }for(i=1;i<=ID-2;i++) Add(i<<1,i<<11,1,0);//每个点拆成两个点，限制流量
    for(i=1;i<=n;i++) if(!G[i][1]) Add(0,idx(i,1)<<1,1,0);
    for(i=1;i<=n;i++) if(!G[i][cnt]) Add(idx(i,cnt)<<11,T,1,0);
    for(i=1;i<=n;i++) if(Add(S,0,1,0),MCMF(),Ans==i) ans[i]=Cost;else n=i-1;
    for(i=1;i<=Q;i++){for(read(x),j=n;~j;j--) if(ans[j]<=x) break ;writeln(j);}return 0;
}