看上去像是一个最大权闭合子图裸题但是数据太大
我们可以先把守卫的视野转换到第二象限(每个守卫可以看到横坐标比他小 纵坐标比他大的宝物) 然后按X从小到大 再按Y从大到小排
这样我们就可以按SORT序遍历守卫 然后贪心地把每个守卫的流量流给离他最近的Y最小的宝物 易证这样是最优的
#include<bits/stdc++.h> #define ll long long using namespace std; inline void read(int &x) { char c; int f = 1; while (!((c = getchar()) >= '0' && c <= '9')) if (c == '-') f = -1; x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') (x *= 10) += c - '0'; if (f == -1) x = -x; } const int maxn = 810000; const double eps = 1e-9; int n, m, N, w, h; struct node { double x, y; int i, c; } X, Y, a[maxn]; inline bool operator <(const node x, const node y) { return x.y - y.y > eps; } inline bool cmp(const node x, const node y) {//按横坐标从小到大，纵坐标从大到小排序 if (fabs(x.x - y.x) < eps) return x.y - y.y < -eps; return x.x - y.x < -eps; } multiset<node>S; multiset<node>::iterator it, it2; node generate(int x, int y) { //视野转换为第二象限 double A = ((double)x / w - (double)y / h) / 2.0; double B = A - (double)x / w; return (node) { -A, -B, 0, 0 }; } ll re; int main() { read(n); read(m); N = n + m; read(w); read(h); //X=(node){w,-h}; //Y=(node){-w,-h}; for (int i = 1; i <= n; i++) { int x, y, c; read(x); read(y); read(c); a[i] = generate(x, y); a[i].i = i; a[i].c = c; re += c; } for (int i = 1; i <= m; i++) { int x, y, c; read(x); read(y); read(c); a[n + i] = generate(x, y); a[n + i].i = n + i; a[n + i].c = c; } sort(a + 1, a + N + 1, cmp); for (int i = 1; i <= N; i++) { if (a[i].i <= n) S.insert(a[i]); else { it = S.lower_bound(a[i]); while (it != S.end() && a[i].c) { it2 = it; it2++; //指向下一个 if (a[i].c < (*it).c) { node tmp = (*it); tmp.c -= a[i].c; re -= a[i].c; S.erase(it); S.insert(tmp); break; } a[i].c -= (*it).c; re -= (*it).c; S.erase(it); it = it2; } } } printf("%lld\n", re); return 0; }