about 4 years ago

看到标题就直接CLICK进去了,看完题目觉得压力山大。。。

题目讲的是这样一个意思:
n个方格,每个方格六个权值a,b,w,l,r,p

1.你现在可以将这个方格染成黑白两种颜色,如果这个方格染成黑色获得b的开心值,染成白色则有w的开心值。
2.如果对于某个 白格子j 满足 1< j < i,且 l[i] < a[j] < r[i] ,则会减少p的开心值。
要你求出最大的开心值。

显然第一眼看到就是最小割,源汇点分别表示黑白两种颜色,每个点向其连边,容量分别为b,w

这个题主要比较特别的,也比较烦人的就是条件2,对此有一个特别的方法:
对于每个点i,新建一个点i',i向i'连一条容量为p的边。
如果j是关于i的符合题意的点,i'向j连一条边。

这样整个图就初步构完了。 然而发现构图是O(N方)的,不满足条件。
由于a的取值在一定的范围内,我们可以构建一颗线段树优化时间。

而显然对于每个点都新建一颗树是不可能的,就想到了主席。

这个故事告诉我们,代码的实现是一条艰辛而漫长的道路,嗯。

BZOJ 2821 作诗 →
 
comments powered by Disqus