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

Posted on Symbols count in article: 1.5k Reading time ≈ 5 mins.

Problem

【JSOI2010】Frozen Nova 冷冻波

Time Limit: 10Sec10 Sec
Memory Limit: 64MB64 MB

Description

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

Input

输入文件第一行包含三个整数N,M,K(N,M,K≤200)N,M,K(N,M,K\le 200)，分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来NN行，每行包含四个整数x,y,r,tx, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。 再接下来MM行，每行两个整数x,yx, y，分别代表了每个小精灵的坐标。 再接下来K行，每行三个整数x,y,rx, y, r，分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过1000010000，半径和施法间隔不超过2000020000。

Output

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

Sample Input

1
2
3
4
5
6
7
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output

1
5

标签：二分 最大流

Solution

这种二分答案+最大流二分答案+最大流是常见套路。类似BZOJ3993BZOJ3993。
二分时间，对于每个时间，判断是否足够消灭所有敌人。
建模：
对于每个巫妖ii，建边 s→is\to i 权值为 time攻击间隔+1\frac{time}{攻击间隔}+1
对于每个精灵jj，建边 j→tj\to t 权值为 11
对于每组两个能攻击到的巫妖aa和精灵bb，建边 a→ba\to b 权值为 11
在次图上跑最大流，判断最大流是否等于m，即是否所有小精灵都有匹配的巫妖。
预处理每个巫妖和每个小精灵之间是否能看到，即用点到直线距离判断树木kk所在的圆是否与巫妖所在点和小精灵所在点两点连成线段有交点，有则不能看到。具体见代码。

Code

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#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;
}