- 一张网格图上有(n)个手办和(m)个警卫,每个手办有一个价值,每个警卫有一个贿赂代价。
- 每个警卫都看向(y)轴负半轴方向,且所有警卫视角一半的正切值都是(frac wh)。
- 你只可以拿走所有不被任何未贿赂的警卫看到的手办,求最大收益。
- (n,mle2 imes10^5)
最大权闭合子图
这东西一眼就是个最大权闭合子图模型。
考虑选择一个手办,相当于所有能看到这个手办的警卫都必须被选择。
也就是说,按照最大权闭合子图的一般套路,我们有这样的建图方式:
- 从超级源向每个警卫连一条容量为对应贿赂代价的边。
- 从每个手办向超级汇连一条容量为对应价值的边。
- 所有警卫向能看到的手办连边。
答案就是所有手办的价值总和减去网络流的最小割(=最大流)。
直接暴力显然(T)飞,因此考虑优化。
推式子
假设我们要判断坐标((x_i,y_i))的警卫能不能看到坐标((x_j,y_j))的手办。
相当于要满足:
[egin{cases}
y_ige y_j,\
x_i-(y_i-y_j) imesfrac whle x_jle x_i+(y_i-y_j) imesfrac wh
end{cases}
]
首先发现当(y_i<y_j)时第二个式子肯定不满足,因此第一个式子完全可以忽略。
而第二个位置我们先给每一项乘上(h)去分母,然后把它拆成两个不等式,再把含(i)的项放一边,含(j)的项放一边,一通变形后得到这样两个式子:
[x_i imes h-y_i imes wle x_j imes h-y_j imes w\
x_i imes h+y_i imes wge x_j imes h+y_j imes w
]
考虑我们把坐标((x,y))转换成((x imes h+y imes w,x imes h-y imes w))。
那么警卫(i)能看到手办(j)的充要条件就是:(x_ige x_j)且(y_ile y_j)。
模拟费用流
首先我们把所有警卫和手办一起按照(x_i)排个序((x_i)相同手办靠前),那么每个警卫只能向他之前的手办连边,(x)这一维限制就消去了。
然后发现每个警卫一定是向(y)的值大于等于他的手办连边,既然求的是最大流,那么肯定优先流(y)最小的手办,因为(y)越大就越可能被其他警卫流到。
于是只要开个(multiset)维护一下就好了。
代码:(O(nlogn))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define LL long long
#define Pr pair<LL,int>
#define mp make_pair
using namespace std;
int n,m,w,h;struct Data
{
LL x,y;int v;I Data(Con LL& a=0,Con LL& b=0,CI c=0):x(a),y(b),v(c){}
I bool operator < (Con Data& o) Con {return x^o.x?x<o.x:v>0;}//按第一维排序,相同时手办在前
}s[2*N+5];multiset<Pr> S;
int main()
{
RI i,x,y,v;scanf("%d%d%d%d",&n,&m,&w,&h);
for(i=1;i<=n;++i) scanf("%d%d%d",&x,&y,&v),s[i]=Data(1LL*x*h+1LL*y*w,1LL*x*h-1LL*y*w,v);//坐标转换
for(i=1;i<=m;++i) scanf("%d%d%d",&x,&y,&v),s[n+i]=Data(1LL*x*h+1LL*y*w,1LL*x*h-1LL*y*w,-v);//坐标转换
Pr k;LL w,t=0;for(sort(s+1,s+n+m+1),i=1;i<=n+m;++i)//模拟费用流
{
if(s[i].v>0) {t+=s[i].v,S.insert(mp(s[i].y,s[i].v));continue;}//对于手办,统计价值总和,并扔入set中
s[i].v*=-1;W(s[i].v&&!S.empty()&&(--S.end())->first>=s[i].y)
S.erase(S.find(k=*S.lower_bound(mp(s[i].y,0)))),//取出y尽可能小的手办
(w=min(s[i].v,k.second),s[i].v-=w,(k.second-=w)&&(S.insert(k),0),t-=w);//计算流量
}return printf("%lld
",t),0;//输出答案
}