题解：P10936 导弹防御塔

wangbinfeng · 2024-09-16 14:05:55 · 题解

前置知识：匈牙利算法（二分图最大匹配），如果不会欢迎阅读我写的另一篇题解。

对于本题来说，因为导弹防御塔与入侵者并不是一一对应（一个导弹防御塔）可以对应若干个敌人，那么考虑将一个导弹防御塔拆成若干个结点。

而多少个结点取决于总用时（即答案），发现答案满足单调性（因为如果能在某一时间内击退敌人，那么时间更长也一定可以），那么可以用二分答案，再用二分的 mid 来拆点（导弹防御塔）。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+9;
const double eps=1e-9;
vector<int>g[maxn];
int n,m,t,ans,match[maxn*maxn];
double t1,t2,v,dis[maxn][maxn],l=0.0,r=1e6;
pair<int,int>a[maxn],b[maxn];
bitset<maxn*maxn>vis;
inline bool dfs(const int u){
    for(int v:g[u])if(!vis[v]){
        vis[v]=true;
        if(!match[v]||dfs(match[v])){match[v]=u;return true;}
    }
    return false;
}
inline bool check(const double lim){
    const int num=min(m,int((lim+t2)/(t1+t2)+eps*0.01));
    //cerr<<"[stderr]"<<fixed<<setprecision(8)<<lim<<' '<<num<<endl;
    for(int i=1;i<=m;i++){
        g[i].clear();
        for(int j=1;j<=n;j++)for(int k=1;k<=num;k++)
            if(dis[i][j]+t1*k+t2*(k-1)<=lim)g[i].push_back((j-1)*num+k);
    }
    memset(match,0,sizeof match);
    for(int i=1;i<=m;i++){
        //cerr<<"[stderr]"<<i<<endl;
        vis.reset();
        if(!dfs(i))return false;
    }
    return true;
}
signed main(){
    // freopen("dat.in","r",stdin);
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>t1>>t2>>v,t1/=60.0;
    for(int i=1,x,y;i<=m;i++)cin>>a[i].first>>a[i].second;
    for(int i=1,x,y;i<=n;i++)cin>>b[i].first>>b[i].second;
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)
            dis[i][j]=sqrt(double(a[i].first-b[j].first)*(a[i].first-b[j].first)+double(a[i].second-b[j].second)*(a[i].second-b[j].second))/v;
    for(double mid=(l+r)/2.0;r-l>eps;mid=(l+r)/2.0)
        if(check(mid))r=mid;
        else l=mid;
    cout<<fixed<<setprecision(6)<<r<<endl;
    //for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cerr<<fixed<<setprecision(2)<<dis[i][j]<<' ';cerr<<endl;}
}