题解 P5996 【[PA2014]Muzeum】

justin_cao · 2020-04-02 16:44:57 · 题解

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

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

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

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

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

那么我们如果将坐标 (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;
}