算法1

(网络流)

自从学了网络流见到二分图就想写，匈牙利告辞:)

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 51 * 51 * 51,M = N * 4;
int mod = 1e9 +7;
int n,m,k,S,T;
int e[M],ne[M],f[M],h[N],idx;
void add(int a,int b,int c){
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
int d[N],cur[N];
bool bfs(){
    queue<int> q;
    q.push(S);
    memset(d,0,sizeof(d));
    d[S] = 1,cur[S] = h[S];
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = h[u] ; ~i ; i = ne[i]){
            int ver = e[i];
            if(!d[ver] && f[i]){
                d[ver] = d[u] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q.push(ver); 
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u] ; ~i && flow < limit ; i = ne[i]){
        int ver = e[i];
        cur[u] = i;
        if(d[ver] == d[u] + 1 && f[i]){
            int k = find(ver,min(f[i],limit - flow));
            if(!k) d[ver] = 0;
            f[i] -= k,f[i ^ 1] += k,flow += k;
        }
    }
    return flow;
} 
int dinic(){
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r += flow;
    return r;
}
int t2,v;
double t1;
struct node{
    int x,y;
}a[N],b[N];
double st[N];
int get(int x,int y){
    return (x - 1) * n + y + m;
}
double get_dis(node a,node b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
bool check(double mid){
    memset(h,-1,sizeof(h));
    idx = 0;
    int cnt = 0;
    //mid时间内每个炮塔能够射出多少枚导弹，导弹数不超过m
    if(mid >= t1) cnt++;
    cnt += (mid - t1) / (t1 + t2); 
    cnt = min(cnt,m);
    S = 0,T = cnt * n + m + 1;
    //从源点向所有射出的导弹连容量为1的边
    for(int i = 1 ; i <= cnt ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            add(S,get(i,j),1);
        }
    }
    //从所有敌人向汇点连容量为1的边
    for(int i = 1 ; i <= m ; ++i) add(i,T,1);
    for(int i = 1 ; i <= cnt ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            for(int k = 1 ; k <= m; ++k){
                //t为该导弹剩余飞行时间
                double t = mid - st[i];
                //若该导弹能在剩余时间内击中敌人则从该导弹向敌人连容量为1的边
                if(get_dis(a[j],b[k]) / v <= t + 1e-8){
                    add(get(i,j),k,1);
                }
            }
        }
    }
    //若能消灭所有敌人则返回true
    return dinic() == m;
}
void solve(){
    cin >> n >> m >> t1 >> t2 >> v;
    for(int i = 1 ; i <= m ; ++i) cin >> b[i].x >> b[i].y;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i].x >> a[i].y;
    //t1单位是秒麻了。。。
    t1 /= 60;
    //预处理第i个导弹的射出时间
    st[1] = t1;
    for(int i = 2 ; i <= m ; ++i){
        st[i] = st[i - 1] + t1 + t2;
    }
    double l = 0,r = 1e6;
    int cnt = 0;
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    printf("%.6lf\n",l);
}

signed main(){
    solve();
    return 0;
}