题目描述

给出 N 座导弹防御塔的坐标，M 个入侵者的坐标，T1 , T2 和 V 。因为Freda的小伙伴Rainbow就要来拜访城堡了，你需要求出至少多少分钟才能击退所有的入侵者。

题目分析

1 答案具有单调性，且直接计算不方便，对其二分
2 构造:构造 N * M作为右部节点，把M个入侵作为左边节点，这个时候把左边的点设计为i * m + j + m,i * m表示是第几个武器，j表示第几发炮弹，最后加m是为了与右边的点区分开来，因为右边是1到m。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const double eps = 1e-8;
int e[N],ne[N],idx,w[N],h[N];
int a[N][2],b[N][2],match[N];
double t1,t2,n,m,v;
bool vis[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

double distance(double x1,double y1,double x2,double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool dfs(int u)
{
    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];
        if(vis[j]) continue;
        vis[j] = true;
        if(match[j] == -1 || dfs(match[j]))
        {
            match[j] = u;
            return true;
        }
    }
    return false;
}

bool check(double mid)
{
    memset(h,-1,sizeof h),memset(match,-1,sizeof match);
    int cnt = -1;
    for(int i = 0;i <= n - 1;i++)
     for(int j = 0;j <= m - 1;j++)
      for(int k = 0;k <= m - 1;k++)
      {
          if(distance(a[k][0],a[k][1],b[i][0],b[i][1]) / v + j * (t1 + t2) + t1 <= mid)
          {
              add(i * m + j + m,k),add(k,i * m + j + m);
          }
      }

    for(int i = 0;i <= m - 1;i++)
    {
        memset(vis,0,sizeof vis);
        if(!dfs(i))
        {
            return false;
        }
    }
    return true;
}

int main()
{
    cin >> n >> m >> t1 >> t2 >> v;
    t1 /= 60;
    for(int i = 0;i <= m - 1;i++)
    {
        cin >> a[i][0] >> a[i][1];
    }
    for(int i = 0;i <= n - 1;i++)
    {
        cin >> b[i][0] >> b[i][1];
    }
    double l = t1,r = 300000,mid;
    while(l + eps < r)
    {
        mid = (l + r) / 2;
        if(check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    printf("%.6f\n",l);
    return 0;
}