自动搬运

查看原文

来自洛谷，原作者为

	justin_cao **

搬运于2025-08-24 22:16:20，当前版本为作者最后更新于2020-04-02 16:44:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

显然这个模型是一个最大权闭合子图的模型，但是直接连边跑显然复杂度爆炸。

于是可以想到最小割$=$最大流，那么考虑贪心模拟费用流。

首先这个坐标系看起来不太舒服，所以考虑转换一下坐标系。

如果一个警卫 $a$ 能够看到一个手办 $b$ ，那么需要满足：

$$\frac{x_a-x_b}{y_a-y_b}\leq \frac{w}{h}$$ $$\frac{x_b-x_a}{y_a-y_b}\leq \frac{w}{h}$$

那么将式子拆开可以得到：

$$x_a\times h-y_a\times w\leq x_b\times h-y_b\times w $$$$x_a\times h+y_a\times w\geq x_b\times h+y_b\times w $$

那么我们如果将坐标 $(x,y)$ 转为坐标 $x\times h+y\times w,x\times h-y\times w$ ，那么限制条件显然就转化为了 $y_a\leq y_b,x_a\geq x_b$ 。

那么考虑将它们按照 $x$ 坐标排序，然后从小到大扫，扫到一个警卫时，由于已经排好序，所以只需要考虑 $y$ 坐标了。

考虑这个警卫向哪些手办流最优。显然往 $y$ 小的流最优（能够看到的），因为 $y$ 越大，能流到它的流就更多，所以要先流小的。

那么用这个贪心策略，我们开一个 $set$ 存一下当前还存在的手办的 $y$ 坐标和剩余的流量，每次用 $set$ 贪心的查找跑流即可。

复杂度$O(n \log n)$。

code：

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,h,w;
struct P{
    ll x,y,v;
}a[maxn],b[maxn];
bool cmp(P a,P b)
{
    return a.x<b.x;
}
set<pair<ll,ll> >s;
ll ans;
int main()
{
    n=read();m=read();w=read();h=read();
    for(int i=1;i<=n;i++)
    {
        ll x=1ll*read()*h,y=1ll*read()*w,v=read();ans+=v;
        a[i].x=x+y;a[i].y=x-y;a[i].v=v;
    }
    for(int i=1;i<=m;i++)
    {
        ll x=1ll*read()*h,y=1ll*read()*w,v=read();
        b[i].x=x+y;b[i].y=x-y;b[i].v=v;
    }
    sort(a+1,a+n+1,cmp);sort(b+1,b+m+1,cmp);
    int now=0;
    for(int i=1;i<=m;i++)
    {
        while(now<n&&a[now+1].x<=b[i].x)  now++,s.insert(make_pair(a[now].y,a[now].v));
        set<pair<ll,ll> >::iterator it=s.lower_bound(make_pair(b[i].y,0));
        ll las=b[i].v;
        while(las&&it!=s.end())
        {
            pair<ll,ll> x=*it;s.erase(it);
            ll d=min(las,(ll)x.second);
            las-=d;x.second-=d;ans-=d;
            if(x.second)  s.insert(x);
            else          it=s.lower_bound(make_pair(b[i].y,0));
        }
    }
    cout<<ans<<endl;
    return 0;
}