PA2025 1A teleport

· · 题解

假设从大到小枚举 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
*/