题解：AT_abc401_g [ABC401G] Push Simultaneously

laiyouming · 2025-04-26 13:15:33 · 题解

思路

先预处理出任意两点间的距离，然后按照路径长度排序，接着二分答案，判断条件是将所有边权小于二分值的边建图，看一下是否是二分图完备匹配，如果是那就将二分值缩小，否则就增大。

代码

#include <bits/stdc++.h>
using namespace std;
int n,top,c[3001],d[3001];
long long s1[301],s2[301],s3[301],s4[301];
vector<pair<long double,pair<int,int>>>a;
vector<int>b[3001];
bool dfs(int x){
    d[x]=1;
    for(auto j:b[x]){
        if(!c[j]||(!d[c[j]]&&dfs(c[j]))){
            c[j]=x;
            return 1;
        }
    }
    return 0;
}
bool ok(long long x){
    for(int i=1;i<=2*n;i++){
        c[i]=0,b[i].clear();
    }
    for(auto i:a){
        if(!x){
            break;
        }
        x--;
        b[i.second.first].push_back(i.second.second);
        b[i.second.second].push_back(i.second.first);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=2*n;j++){
            d[j]=0;
        }
        if(dfs(i)){
            ans++;
        }
    }
    if(ans==n){
        return 1;
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&s1[i],&s2[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&s3[i],&s4[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            top++;
            a.push_back({sqrt((__int128)abs(s1[i]-s3[j])*abs(s1[i]-s3[j])+(__int128)abs(s2[i]-s4[j])*abs(s2[i]-s4[j])),{i,n+j}});
        }
    }
    sort(a.begin(),a.end());
    long long l=0,r=top+1;
    for(;l+1<r;){
        long long x=(l+r)/2;
        if(ok(x)){
            r=x;
        }
        else{
            l=x;
        }
    }
    printf("%.20Lf",a[r-1].first);
}
```c