题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=1822
题解
好久没做网络流的，都没有想到网络流...
首先暴力判断一下一个巫妖和一个精灵之间能否攻击到。大体上就是枚举树，求一下圆心到巫妖和精灵的连线段的距离，和半径比较一下就可以了。
然后巫妖向能攻击到的精灵建边。然后二分答案 \(mid\)，从 $S $ 向每个精灵建一条容量为 \(\lfloor\frac {mid}t\rfloor + 1\) 的边，每个精灵向 \(T\) 建一个 \(1\) 的边。跑最大流就可以了。
下面是代码。因为这是一个二分图，所以一次 Dinic 的复杂度为 \(O(m\sqrt n) = O(n^{\frac 52})\)。因此总的时间复杂度为 \(O(\operatorname{Dinic}(n, n^2)\log ans)\)。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I>
inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int NN = 200 + 7;
const int N = 200 * 2 + 2 + 7;
const int M = 200 * 200 + 200 * 2 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;
int n, m, k, nod, allsize, S, T, tot1, mxt, hd, tl;
int ar[NN], at[NN], cr[NN];
int dis[N], cur[N], q[N];
struct Point {
int x, y;
inline Point() {}
inline Point(const int &x, const int &y) : x(x), y(y) {}
} a[NN], b[NN], c[NN];
inline Point operator - (const Point &a, const Point &b) { return Point(a.x - b.x, a.y - b.y);}
inline int dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
inline int cross(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x;}
//inline double dist(const Point &a, const Point &b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
inline int dist2(const Point &a, const Point &b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }
struct Edge { int to, ne, f; } g[M << 1]; int head[N], tot = 1;
inline void addedge(int x, int y, int z) { g[++tot].to = y, g[tot].f = z, g[tot].ne = head[x], head[x] = tot;}
inline void adde(int x, int y, int z) { addedge(x, y, z), addedge(y, x, 0); }
inline bool bfs() {
memset(dis, 0x3f, allsize), memcpy(cur, head, allsize);
q[hd = 0, tl = 1] = S, dis[S] = 0;
while (hd < tl) {
int x = q[++hd];
for fec(i, x, y) if (g[i].f && dis[y] == INF) {
dis[y] = dis[x] + 1, q[++tl] = y;
if (y == T) return 1;
}
}
return 0;
}
inline int dfs(int x, int a) {
if (x == T || !a) return a;
int flow = 0, f;
for (int &i = cur[x]; i; i = g[i].ne) {
int y = g[i].to;
if (dis[y] != dis[x] + 1 || !(f = dfs(y, std::min(a, g[i].f)))) continue;
g[i].f -= f, g[i ^ 1].f += f;
flow += f, a -= f;
if (!a) break;
}
if (!flow) dis[x] = INF;
return flow;
}
inline int dinic() {
int ans = 0;
while (bfs()) ans += dfs(S, INF);
return ans;
}
inline void build() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) if (dist2(a[i], b[j]) <= ar[i] * ar[i]) {
bool flag = 1;
for (int kk = 1; kk <= k; ++kk) {
int s = abs(cross(b[j] - a[i], c[kk] - a[i]));
if ((ll)dot(c[kk] - b[j], a[i] - b[j]) * dot(c[kk] - a[i], b[j] - a[i]) > 0 && (ll)s * s <= (ll)cr[kk] * cr[kk] * dist2(b[j], a[i])) { flag = 0; break; }
if (dist2(c[kk], b[j]) <= cr[kk] * cr[kk] || dist2(c[kk], a[i]) <= cr[kk] * cr[kk]) { flag = 0; break; }
}
if (flag) adde(i, j + n, 1);
}
S = n + m + 1, nod = T = S + 1, allsize = (nod + 1) * sizeof(int);
for (int i = 1; i <= m; ++i) adde(i + n, T, 1);
tot1 = tot;
for (int i = 1; i <= n; ++i) adde(S, i, 0);
}
inline bool check(const int &mid) {
for (int i = 2; i <= tot1; i += 2) g[i].f = 1, g[i ^ 1].f = 0;
for (int i = 1, j = tot1 + 1; i <= n; ++i, j += 2) g[j].f = mid / at[i] + 1, g[j ^ 1].f = 0;
return dinic() >= m;
}
inline void work() {
build();
int l = 0, r = mxt * m;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (!check(l)) puts("-1");
else printf("%d\n", l);
}
inline void init() {
read(n), read(m), read(k);
for (int i = 1; i <= n; ++i) read(a[i].x), read(a[i].y), read(ar[i]), read(at[i]), smax(mxt, at[i]);
for (int i = 1; i <= m; ++i) read(b[i].x), read(b[i].y);
for (int i = 1; i <= k; ++i) read(c[i].x), read(c[i].y), read(cr[i]);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}