bzoj4977 跳伞求生
这道题比较简单
直接考虑按子弹数从小到大排序，扫到敌人加进堆里
扫到一个队友就考虑是匹配一个敌人或者是替换掉以前一个队友
这里满足偏序关系并且敌人是不能反悔换掉原来选择的一个敌人的
所以正确性有保障
「ICPC World Finals 2018」征服世界
这道题的最小费用最大流建图还是比较好想
首先我们把每一个终点的权值设为-inf
这样就把最小费用最大流转成了最小费用流
就可以考虑模拟费用流了
这道题的军队移动你选择的配对的起止点都是可以反悔的
注意到两个点之间的距离是
(dis[x]+dis[y]-2*dis[lca(x,y)])
其中dis是根节点到该点的距离
那么我们考虑把dis作为一个点的权值然后枚举lca计算答案
假设在一个点的子树z内
选择了起点x点和终点y点配对
我们就在起点的堆里加入-dis[y]+dis[z]*2
在终点的堆里加入-dis[x]+dis[z]*2
这样就可以在祖先处反悔
每一个点枚举两个堆的堆顶判断是否反悔即可
利用可并堆实现
「NOI2019」序列
这个题比较神
最大费用最大流建图需要一些思考
A集合每个数拆一个点
B集合每个数拆一个点
再加X，Y两个点
S，T总流量为k
(S->A_i （1,a_i))
(A_i->B_i (1,0))
(B_i->T (1,B_i))
这里就表示选择相同下标的可以选择最多k个
(A_i->X (1,0))
(X->Y (k-l,0))
(Y->B_i (1,0))
这里就表示(A_i)和(B_j)可以配对
但是最多配(k-l)个
这里由于题解说的我们发现他不会反悔
只会更改A与B之间的匹配方案
也就是不会放弃选某个A或某个B
只会更改原来与某个B匹配的A去变成另一个A
那么我们就可以考虑每一次添加1流量计算答案
理性思考发现新增一个流只有五种情况
我们记自由匹配表示(A_i->B-j)这种情况
(S->A_i->B_i->T)
选择一组(A_i)和(B_i)都没被选的配对，这时自由匹配数不变
(S->A_i->X->Y->B_j->T)
选择一个(A_i)和(B_j)配对，这时自由匹配数+1
(S->A_i->B_i->Y->X->A_j->B_j->T)
选择一个原来(B_i)和(A_j)都在匹配中的(A_i)和(B_j)配对
此时我们调整一下
把(A_i)换去和(A_j)配
把(B_i)换去和(B_j)配
此时自由匹配数会-1
(S->A_i->B_i->Y->B_j)
(S->A_i->X->A_j->B_j)
这两个都是选一个另外一个已经在匹配中的去配对
调整一下使得自由匹配数不变
于是我们只需要维护5个堆
维护一下
(a_i+b_i,a_i,b_i)(两个都没被选)
(a_i,b_i)((b_i/a_i)被选)
每次取最大的增广就好了
「LibreOJ NOI Round #2」黄金矿工
扔树上搞