BZOJ1822【JSOI2010】Frozen Nova 冷冻波 <二分+最大流>

Problem

【JSOI2010】Frozen Nova 冷冻波

Time Limit:
Memory Limit:

Description

喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。 在森林里有个巫妖，每个巫妖释放之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道，若从时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？

Input

输入文件第一行包含三个整数，分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来行，每行包含四个整数，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。 再接下来行，每行两个整数，分别代表了每个小精灵的坐标。 再接下来K行，每行三个整数，分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过，半径和施法间隔不超过。

Output

输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出。

Sample Input

2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output

5

标签：二分 最大流

Solution

这种是常见套路。类似。
二分时间，对于每个时间，判断是否足够消灭所有敌人。
建模：
对于每个巫妖，建边 权值为
对于每个精灵，建边 权值为
对于每组两个能攻击到的巫妖和精灵，建边 权值为
在次图上跑最大流，判断最大流是否等于m，即是否所有小精灵都有匹配的巫妖。
预处理每个巫妖和每个小精灵之间是否能看到，即用点到直线距离判断树木所在的圆是否与巫妖所在点和小精灵所在点两点连成线段有交点，有则不能看到。具体见代码。

Code

(我预处理的计算几何部分较为复杂，可以参考hzwer的代码，要简洁一些。)

#include <bits/stdc++.h>
#define MAX_N 200
#define MAX_M 500000
#define INF 0x7f7f7f7f
using namespace std;
typedef double dnt;
int n, m, k, s, t, mx, cnt, pr[MAX_N*2+5];
struct WIZ {int x, y, r, t;} wiz[MAX_N+5];
struct ELF {int x, y;} elf[MAX_N+5];
struct TRE {int x, y, r;} tre[MAX_N+5];
struct EDG {int u, v, c, nxt;} E[MAX_M+5];
int d[MAX_N*2+5], cr[MAX_N*2+5];
bool mrk[MAX_N+5][MAX_N+5];

//---------- Geometry Section ----------//
WIZ operator - (WIZ a, TRE b) {WIZ t; t.x = a.x-b.x, t.y = a.y-b.y; return t;}
WIZ operator - (TRE a, WIZ b) {WIZ t; t.x = a.x-b.x, t.y = a.y-b.y; return t;}
ELF operator - (ELF a, TRE b) {ELF t; t.x = a.x-b.x, t.y = a.y-b.y; return t;}
ELF operator - (ELF a, WIZ b) {ELF t; t.x = a.x-b.x, t.y = a.y-b.y; return t;}
dnt dot(WIZ a, ELF b) {return a.x*b.x+a.y*b.y;}
dnt cross(WIZ a, ELF b) {return a.x*b.y-a.y*b.x;}
dnt dis(WIZ a, ELF b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
dnt dis(WIZ a, TRE b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
dnt dis(ELF a, TRE b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
dnt dis(WIZ a, ELF b, TRE p) {
    if (dot(a-p, b-p) > 0)
        return min(dis(a, p), dis(b, p));
    return abs(cross(p-a, b-a)/dis(a, b));
}
bool jud(int x, int y) {
    if (dis(wiz[x], elf[y]) > wiz[x].r) return false;
    for (int i = 1; i <= k; i++)
        if (dis(wiz[x], elf[y], tre[i]) < tre[i].r) return false;
    return true;
}

//---------- Network Flow Section ----------//
void init() {s = 0, t = n+m+1, cnt = 0; memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pr[u], pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (!c || ~d[v]) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t)	return flow;
    int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (!c || d[v] != d[u]+1) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;
    return ret;
}
int Dinic() {
    int ret = 0;
    for (int i = s; i <= t; i++) cr[i] = pr[i];
    while (BFS()) {
        ret += DFS(s, INF);
        for (int i = s; i <= t; i++) pr[i] = cr[i];
    }
    return ret;
}

//---------- Binary Search Section ----------//
bool chk(int tans) {
    init();
    for (int i = 1; i <= n; i++) addedge(s, i, tans/wiz[i].t+1);
    for (int i = 1; i <= m; i++) addedge(i+n, t, 1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        if (mrk[i][j]) addedge(i, j+n, 1);
    return Dinic() == m;
}
int bi_search(int l, int r) {
    int ret = -1;
    while (l <= r) {
        int mid = (l+r)>>1;
        if (chk(mid)) r = mid-1, ret = mid;
        else l = mid+1;
    }
    return ret;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &wiz[i].x, &wiz[i].y, &wiz[i].r, &wiz[i].t), mx = max(wiz[i].t, mx);
    for (int i = 1; i <= m; i++) scanf("%d%d", &elf[i].x, &elf[i].y);
    for (int i = 1; i <= k; i++) scanf("%d%d%d", &tre[i].x, &tre[i].y, &tre[i].r);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) mrk[i][j] = jud(i, j);
    return printf("%d", bi_search(0, m*mx)), 0;
}