自动搬运

查看原文

来自洛谷，原作者为

	Miko35 阿玮你又在打电动喔，去看会书好不好

搬运于2025-08-24 22:28:18，当前版本为作者最后更新于2022-02-22 14:38:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Orz EA!

首先你发现，向上流和向下流实际上是一样的，左右同理，并且操作顺序是没有关系的，所以一定存在一种最优策略是下移 $A$ 次后右移 $B$ 次，此时一个点会向右向下延伸出一个 $(A+1) \times (B+1)$ 的矩形。

考虑两个黑点 $(x,y) \to (x',y')$ 啥时候能联通（不妨 $x<x'$, $y<y'$），那就是 $A \ge x'-x-1$，$B \ge y'-y-1$ 的时候。最暴力的想法是，把两黑点间连一条权值为二元组 $(x'-x-1,y'-y-1)$ 的边，那我们就要求的是 $\max x + \max y$ 的 MST。

一种求法是枚举 $\max x$ 然后计算 $\max y$ 的最小值。具体而言，将所有 $M$ 条边按照 $x$ 从小到大排序，逐条加入进来，同时 LCT 维护 $y$ 这维的 MST，可以 $O(M \log n)$。当然也可以 $O(M \log^2 M)$ 整体二分，比较好写。

黑点数较多时 $M$ 可以到 $O(n^2m^2)$ 的级别，但其实有很多边是不需要的：以两个黑点 $p,q$ 为对角的矩形内，如果还存在其他黑点，则这条边就不需要了，因为可以由这两条较短的边“拼合”起来得到。这样连边的话，显然同一行内的点连出的边是 $O(m)$ 级别，故总边数是 $O(nm)$ 级别的。套用上面求 MST 的做法，我们就以 $O(nm \log nm)$ 的复杂度解决了这道题。

可能会卡常，但显而易见这个 $O(nm)$ 的边数很难卡到很满。有一个有力的剪枝：一开始存在于一个连通块的黑点可以直接缩起来。

这份代码是 $O(nm \log n \log m)$ 的整体二分，可以比较快跑过去。

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(int i=a,i##i=b;i>=i##i;--i)
using namespace std;
const int N=1e3+7,M=3*N*N;
int n,m,C=1,lm,ct[M],T,ans[N],h[N],id[N],res=M,X[N],Y[N],g;
char s[N];
struct mem{int t,p,v;};
struct unf{
	int a[M],C=0;mem f[M];
	int& operator[](int x){return a[x];}
	void st(int x,int v){f[++C]={T,x,a[x]},a[x]=v;}
	void rbk(int t){for(;C&&f[C].t>=t;--C)a[f[C].p]=f[C].v;}
}fa,rk;
int rbk(int t){return fa.rbk(t),rk.rbk(t),T=t-1;}
int fd(int x){return fa[x]==x?x:fd(fa[x]);}
int merge(int x,int y){
	x=fd(x),y=fd(y);
	if(x!=y){
		if(rk[x]<rk[y])swap(x,y);
		ct[T+1]=ct[T]-1,++T,fa.st(y,x);
		if(rk[x]==rk[y])rk.st(x,rk[x]+1);
	}
	return ct[T]==1;
}
struct edge{
	int u,v,x,y;
	void mtn(){
		u=fd(u),v=fd(v);
		if(u==v)x=m+1,y=n+1;
	}
	int add(int o){return x<=o?merge(u,v):0;}
}x[M],y[M];
void solve(int l,int r,int L,int R){
	if(L==R)FOR(i,l,r)ans[i]=L;
	if(l>r||L>R)return;
	int d=(l+r)/2,G,t=T+1,p=R;
	FOR(i,X[l],X[d+1]-1)if(x[i].y<L)x[i].add(M);
	G=T+1;
	FOR(i,Y[L],Y[R+1]-1)if(y[i].add(d)){p=y[i].y;break;}
	ans[d]=p,rbk(G),solve(d+1,r,L,p),rbk(t);
	FOR(i,Y[L],Y[p]-1)y[i].add(l-1);
	solve(l,d-1,p,R);
}
void link(int i,int j){
	if(id[i]&&id[j])++C,x[C]=y[C]={id[i],id[j],max(j-i-1,0),max(abs(h[j]-h[i])-1,0)};
}
signed main(){
	scanf("%d%d",&n,&m),lm=max(n,m);
	FOR(i,1,n){
		scanf("%s",s+1),s[m+1]='1';
		int w=1;
		FOR(j,1,m)if(s[j]=='1'){
			if(id[j])++C,x[C]=y[C]={ct[0]+1,id[j],0,i-h[j]-1};
			g=h[j],id[j]=++ct[0],h[j]=i;
			for(int p=j-1,k=g;p>=w;--p)if(h[p]>k)k=h[p],link(p,j);
			for(int p=j+1,k=g;s[p]<'1';++p)if(h[p]>k)k=h[p],link(j,p);
			w=j;
		}
	}
	FOR(i,1,ct[0])fa[i]=i;
	FOR(i,1,C)if(!x[i].y)x[i].add(0);
	FOR(i,1,C)x[i].mtn(),y[i].mtn();
	sort(x+1,x+C+1,[](edge a,edge b){return a.x<b.x;});
	sort(y+1,y+C+1,[](edge a,edge b){return a.y<b.y;});
	while(x[C-1].y>n)--C;
	ROF(i,C,1)X[x[i].x]=Y[y[i].y]=i;
	ROF(i,m,1)if(!X[i])X[i]=X[i+1];
	ROF(i,n,1)if(!Y[i])Y[i]=Y[i+1];
	Y[n+2]=C+1,X[m+2]=C+1,solve(0,m,0,n+1);
	FOR(i,0,m)if(ans[i]<=n)res=min(res,i+ans[i]);
	printf("%d",res);
	return 0;
}