Luogu

分析

不难看出一个最大权闭合子图的模型，然而直接求最大流显然过不了，于是可以考虑模拟最大流。

首先把这个坐标系变换一下。如果警卫 $a$ 能看到手办 $b$，则应有
$$
-\frac{w}{h}\leq \frac{x_a-x_b}{y_a-y_b}\leq\frac{w}{h}
$$
推一推可以得到
$$
\begin{cases}
h\times x_a-w\times y_a\leq h\times x_b-w\times y_b\\
h\times x_a+w\times y_a\geq h\times x_b+w\times y_b
\end{cases}
$$
于是可以把 $(h\times x+w\times y,h\times x-w\times y)$ 作为每个点的坐标，这样子警卫 $a$ 能看到手办 $b$ 当且仅当 $x_b\leq x_a,y_a\leq y_b$。

考虑把所有点按照变换后的横坐标从小到大排序，则我们每次只需要考虑纵坐标了。

假设当前扫到了一个警卫，则我们需要流一些流量，贪心地想一想可以发现往纵坐标尽量小的手办流更好，因为纵坐标大的能被更多的警卫看到。

于是只需要开一个 std::multiset 维护一下所有还没流满的手办及其纵坐标，每次二分一下即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,w,h;
struct node { ll x,y,w; } a[N],b[N];
bool operator <(node a,node b) { return a.x<b.x; }
multiset<pair<ll,int> > S;

int main() {
    n=read(),m=read(),w=read(),h=read(); ll ans=0;
    for (int i=1;i<=n;++i) {
        ll x=1ll*read()*h,y=1ll*read()*w,c=read();
        a[i]=(node){x+y,x-y,c},ans+=c;
    }
    for (int i=1;i<=m;++i) {
        ll x=1ll*read()*h,y=1ll*read()*w,c=read();
        b[i]=(node){x+y,x-y,c};
    }
    sort(a+1,a+n+1),sort(b+1,b+m+1);
    for (int i=1,j=1;i<=m;++i) {
        while (j<=n&&a[j].x<=b[i].x) S.insert(mp(a[j].y,j)),++j;
        while (b[i].w&&!S.empty()) {
            auto it=S.lower_bound(mp(b[i].y,0));
            if (it==S.end()) break;
            int p=it->second,f=min(a[p].w,b[i].w);
            ans-=f,a[p].w-=f,b[i].w-=f;
            if (!a[p].w) S.erase(it);
        }
    }
    printf("%lld\n",ans);
    return 0;
}