2010-1079

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题意 ==
有N个炮塔要打M个目标。一颗炮弹发射后需要T1才能离开炮塔，一颗炮弹发射完后需要T2时间才能发射下一刻。炮弹的飞行速度为V，给定各个炮塔和各个目标的坐标，求最少需要多少时间才能打中所有目标。

== 题解 ==
二分时间，然后根据时间建立二分图，把一个炮塔拆成好几个点，分别表示第1次发射，第2次发射……如果某次发射能击中目标，则连一条边到表示目标的点上。求一下最大匹配，如果最大匹配是M，则继续二分左边的区间[left，middle], 否则则二分区间[middle, right]。

== 代码 ==

{{{
#!cpp
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 64
#define MAXM 64
#define MAXSZ MAXN*MAXM
using namespace std;
class Hungary {
    vector<int> e[MAXN];
    int n, m, match[MAXN], rmatch[MAXM];
    bool vis[MAXN];
    bool _augment(int u) {
        if(!vis[u]) {
            vis[u] = true;
            vector<int>::iterator it;
            for(it = e[u].begin(); it != e[u].end(); ++it) {
                if(rmatch[*it] == -1 || _augment(rmatch[*it])) {
                    match[u] = *it;
                    rmatch[*it] = u;
                    return true;
                }
            }
        }
        return false;
    }
public:
    void init(int n) {
        this->n = n;
        for(int i = 0; i < n; ++i)
            e[i].clear();
    }
    void addEdge(int u, int v) {
        e[u].push_back(v);
    }
    int maxMatch(int m) {
        this->m = m;
        int cnt = 0;
        fill(match, match + n, -1);
        fill(rmatch, rmatch + m, -1);
        for(int i = 0; i < n; ++i) {
            fill(vis, vis + n, false);
            if(_augment(i)) {
                ++cnt;
            }
        }
        return cnt;
    }
} h;
class IDSet {
    int data[MAXSZ];
    int sz;
public:
    void init(int n) {
        fill(data, data + n, -1);
        sz = 0;
    }
    int getId(int num) {
        if(data[num] == -1) {
            data[num] = sz++;
        }
        return data[num];
    }
    int size() {
        return sz;
    }
} ids;
int main() {
    int n, m, v;
    double t1, t2;
    int tx[MAXM], ty[MAXM];
    double d[MAXN][MAXM];
    while(scanf("%d%d%lf%lf%d", &n, &m, &t1, &t2, &v) != EOF) {
        t1 /= 60;
        for(int i = 0; i < m; ++i)
            scanf("%d%d", &tx[i], &ty[i]);
        double maxt = 0;
        for(int i = 0; i < n; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            for(int j = 0; j < m; ++j) {
                d[i][j] = hypot(x - tx[j], y - ty[j]) / v;
                maxt = max(maxt, d[i][j]);
            }
        }
        double le = 0, ri = (m + n - 1) / n * (t1 + t2) + maxt;
        //printf("%lf %lf\n", le, ri);
        while(ri - le > 1e-7) {
            double mi = (le + ri) / 2;
            ids.init(n * m);
            h.init(m);
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < m; ++j) {
                    double t = t1;
                    for(int k = 0; k < m && t + d[i][j] <= mi; ++k) {
                        //printf("%d %d %d\n", i, k, j);
                        h.addEdge(j, ids.getId(i * m + k));
                        t += t1 + t2;
                    }
                }
            }
            int ret = h.maxMatch(ids.size());
            //printf("%lf %lf %d %d\n", le, ri, ret, m);
            if(ret == m)
                ri = mi;
            else
                le = mi;
        }
        printf("%.6lf\n", le);
    }
}
}}}

题意

有N个炮塔要打M个目标。一颗炮弹发射后需要T1才能离开炮塔，一颗炮弹发射完后需要T2时间才能发射下一刻。炮弹的飞行速度为V，给定各个炮塔和各个目标的坐标，求最少需要多少时间才能打中所有目标。

题解

二分时间，然后根据时间建立二分图，把一个炮塔拆成好几个点，分别表示第1次发射，第2次发射……如果某次发射能击中目标，则连一条边到表示目标的点上。求一下最大匹配，如果最大匹配是M，则继续二分左边的区间[left，middle], 否则则二分区间[middle, right]。

代码

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 64
#define MAXM 64
#define MAXSZ MAXN*MAXM
using namespace std;
class Hungary {
    vector<int> e[MAXN];
    int n, m, match[MAXN], rmatch[MAXM];
    bool vis[MAXN];
    bool _augment(int u) {
        if(!vis[u]) {
            vis[u] = true;
            vector<int>::iterator it;
            for(it = e[u].begin(); it != e[u].end(); ++it) {
                if(rmatch[*it] == -1 || _augment(rmatch[*it])) {
                    match[u] = *it;
                    rmatch[*it] = u;
                    return true;
                }
            }
        }
        return false;
    }
public:
    void init(int n) {
        this->n = n;
        for(int i = 0; i < n; ++i)
            e[i].clear();
    }
    void addEdge(int u, int v) {
        e[u].push_back(v);
    }
    int maxMatch(int m) {
        this->m = m;
        int cnt = 0;
        fill(match, match + n, -1);
        fill(rmatch, rmatch + m, -1);
        for(int i = 0; i < n; ++i) {
            fill(vis, vis + n, false);
            if(_augment(i)) {
                ++cnt;
            }
        }
        return cnt;
    }
} h;
class IDSet {
    int data[MAXSZ];
    int sz;
public:
    void init(int n) {
        fill(data, data + n, -1);
        sz = 0;
    }
    int getId(int num) {
        if(data[num] == -1) {
            data[num] = sz++;
        }
        return data[num];
    }
    int size() {
        return sz;
    }
} ids;
int main() {
    int n, m, v;
    double t1, t2;
    int tx[MAXM], ty[MAXM];
    double d[MAXN][MAXM];
    while(scanf("%d%d%lf%lf%d", &n, &m, &t1, &t2, &v) != EOF) {
        t1 /= 60;
        for(int i = 0; i < m; ++i)
            scanf("%d%d", &tx[i], &ty[i]);
        double maxt = 0;
        for(int i = 0; i < n; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            for(int j = 0; j < m; ++j) {
                d[i][j] = hypot(x - tx[j], y - ty[j]) / v;
                maxt = max(maxt, d[i][j]);
            }
        }
        double le = 0, ri = (m + n - 1) / n * (t1 + t2) + maxt;
        //printf("%lf %lf\n", le, ri);
        while(ri - le > 1e-7) {
            double mi = (le + ri) / 2;
            ids.init(n * m);
            h.init(m);
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < m; ++j) {
                    double t = t1;
                    for(int k = 0; k < m && t + d[i][j] <= mi; ++k) {
                        //printf("%d %d %d\n", i, k, j);
                        h.addEdge(j, ids.getId(i * m + k));
                        t += t1 + t2;
                    }
                }
            }
            int ret = h.maxMatch(ids.size());
            //printf("%lf %lf %d %d\n", le, ri, ret, m);
            if(ret == m)
                ri = mi;
            else
                le = mi;
        }
        printf("%.6lf\n", le);
    }
}