1.9测试总结

ZJOI2010..
--------------------------------------------------------
 
T1:
这个
--------------------------------------------------------
T2:
跑一个最大流
然后在残余网络上加边:复制一遍原来的边,容量改为inf,费用改为扩容的费用
另外新建汇点,从原来的汇点向新汇点连边,容量为k,费用为0
跑费用流即可
--------------------------------------------------------
T3:
考虑DP:f(i,j)第i个,已经建了j个基站了,并且第i个点一定要建
转移:f(i,j) = min{f(q,j-1)+cost(q,i)}
其中cost(q,i)表示q,i两点有基站,[q,i]中其他点都没有基站,所有没被覆盖的点的赔偿费用之和
这样就有40分啦
然后,考虑枚举j,再枚举i
在一个线段树中存一下f(q,j-1)+cost(q,i)
询问一下最小值就好啦
f(q,j-1)倒是好办,上一次弄完加进去就行了,cost(q,i)呢?
考虑,当得到f(i,j)后,如果要在i后面的点建基站
那么右界刚好为i的村庄坑定是要被覆盖了
当然前提是它的左界以内也没有建基站
因此在线段树中[1,l-1]的部分加一个赔偿费用,表示如果要从这些点转移,是要赔偿的
然后复杂度就是O(n*k*lgn)的
--------------------------------------------------------