题目传送门

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;

}