自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 23:11:20，当前版本为作者最后更新于2025-03-20 14:46:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

假设从大到小枚举 $ans$，同时维护当前的每个连 $(u,v)$ 是否可行。

关键观察：对于一个 $i$，连 $(u,v)$ 且 $dis(i,u)\le dis(i,v)$ 的话，如果 $dis(i,k)>ans$，从 $i\to k$ 走的方法一定是 $i\to u\to v\to k$。

对于每个 $i$ 分别做以下过程：对于 $dis(i,k) > ans$（即不合法的点），只需要对所有 $v$ 维护 $\max(dis(v,k))$，然后把 $dis(i,u)+\max(dis(v,k))>ans$ 的 $(u,v)$ 弹掉。

时间复杂度 $O(n^3)$。

#define maxn 505
#define inf 0x3f3f3f3f

int n,dis[maxn][maxn];
char s[maxn];
int c[maxn][maxn],all;
int mx[maxn][maxn],p[maxn][maxn];

void sub(int u,int v){
	if(u>v)swap(u,v);
	if(c[u][v])c[u][v]=0,--all;
}

int ps[maxn],qs[maxn][maxn];
void work(int up){
//	cout<<"work "<<up<<endl;
	For(i,1,n){
		int *p=::p[i];
		while(dis[i][p[ps[i]]]>up){
			int u=p[ps[i]];
			For(j,1,n)
				mx[i][j]=max(mx[i][j],dis[p[j]][u]);
			--ps[i];
		}
		if(ps[i]==n) continue;
		For(j,1,n){
			int v=p[j];
			while(qs[i][j]>=1){
				int u=p[qs[i][j]];
				if(dis[i][u]+mx[i][j]<=up) break;
		//		cout<<"sub "<<i<<" "<<u<<" "<<v<<endl;
				sub(u,v);
				--qs[i][j];
			}
			// dis(i,u) + mx[v] > up: baodiao u
		}
	}
//	For(i,1,n){
//		For(j,i+1,n) cout<<c[i][j]<<" "; cout<<"\n";
//	}
}

void work()
{
	n=read();
	For(i,1,n){
		scanf("%s",s+1);
		For(j,1,n)dis[i][j]=(s[j]&1)?1:inf;
		dis[i][i]=0;
	}
	For(k,1,n)For(i,1,n)For(j,1,n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	all=0;
	For(i,1,n)For(j,i+1,n)c[i][j]=n,++all;
	For(i,1,n){
		For(j,1,n)p[i][j]=j;
		sort(p[i]+1,p[i]+n+1,[&](int u,int v){
			return dis[i][u]<dis[i][v];
		});
		ps[i]=n;
		For(j,1,n) qs[i][j]=j-1,mx[i][j]=-inf;
	}
	Rep(i,n-1,1){
		work(i);
		if(!all){
			cout<<i+1<<endl;
			return;
		}
	}
	cout<<1<<endl;
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*
2
4
0111
1011
1101
1110
5
01000
10100
01010
00101
00010
*/