一类老鼠进洞模型

问题描述

给定一个序列,序列上有若干\(mouse\)和若干\(hole\),求一组最优的\(mouse\)和\(hole\)的匹配。
定义一只\(mouse\)跑到一个洞\(hole\)的代价为两点之间的距离。

问题一:洞有容量、有代价 ;

每一个洞不一定要进老鼠,但每一个老鼠一定要进一个洞。

结论一:匹配不会交叉。(显然)
结论二:对于一组匹配,老鼠和洞不会同时反悔。(从左往右进行匹配,同时反悔会产生交叉)

然后就可以用堆模拟费用流啦。
对老鼠和洞分别维护一个堆,设老鼠堆为\(Q_1\),洞的堆为\(Q_2\),表示增广集合。
方便起见先往\(Q_2\)中放一个代价为\(inf\)、容量为\(inf\)的洞。

  • 当碰到一只老鼠时(位置为\(x\)),
    从\(Q_2\)中取出一个洞的增广路,设代价为\(val\)。
    由于老鼠必须匹配,所以答案加上匹配代价\(w = x + val\)。
    这只老鼠可以与后面的洞匹配,所以往\(Q_1\)中加入反悔操作\(-w - x\) 。
  • 当碰到一个洞时(位置为\(x\),代价为\(cost\)),
    依次从\(Q_1\)中取出老鼠\(u\),直到\(Q_1\)为空或者这个洞的容量被用完或者本次匹配不优。
    获取匹配流量\(fl = min(容量 , u.flow)\),
    那么本次匹配量就为\(fl\),答案加上\(fl \times\)本次代价\(w = u.val + x + cost\)。
    由于洞有代价,所以会有两种反悔。
    • 洞反悔,匹配之后的老鼠,在\(Q_2\)中加入代价为\(-w + u.val - x\)的洞。
    • 老鼠反悔,匹配后面的洞,在\(Q_1\)中加入代价为\(-w + val\)的老鼠。
    直接这样\(Q_1\)的复杂度显然是假的,老鼠进堆的复杂度没有保障。
    但是注意到老鼠反悔的代价都是\(-w + val = -x - cost\),都是一样的所以可以只扔一次。
    记录一下这个洞匹配的老鼠个数\(cnt\),这样每个洞就只会往老鼠堆中扔一次啦!
    我们已经知道老鼠和洞不会同时反悔,所以直接把这两种反悔都扔到对应堆中即可。

代码实现相当简单:

Q2.push((Item){inf , 1000000000}) ; Ans = 0 ;
Item u ; ll t , w , fl , cnt ; 
for(int i = 1; i <= n; i ++) {
    if(!p[i].op) {
        u = Q2.top() ;
        Q2.pop() ;
        w = u.val + p[i].x ; Ans += w ; u.flow -- ;
        if(u.flow > 0) Q2.push(u) ;
        Q1.push((Item){- w - p[i].x , 1}) ; 
    }
    else {
        cnt = 0 ; 
        while(p[i].cap && !Q1.empty()) {
            u = Q1.top() ; 
            w = p[i].x + u.val + p[i].cost ; if(w >= 0) break ;
            Q1.pop() ;
            fl = min(p[i].cap , u.flow) ;
            Ans = Ans + 1ll * w * fl ;
            u.flow -= fl ;
            p[i].cap -= fl ; 
            cnt += fl ;
            if(u.flow > 0) Q1.push(u) ;
            Q2.push((Item){- w + p[i].cost - p[i].x , fl}) ;
        }
        if(p[i].cap > 0) Q2.push((Item){- p[i].x + p[i].cost , p[i].cap}) ;
        if(cnt > 0) Q1.push((Item){- p[i].cost - p[i].x , cnt}) ;
    }
}
cout << Ans << endl ; return 0 ;

问题二:洞有容量、有代价 ; 老鼠有容量、有代价

堆模拟费用流,但复杂度没有保证。
对老鼠和洞都进行两种反悔(即老鼠和洞都使用问题二中洞的反悔方式)。
常见转换有:若一个洞必须进老鼠、或者一只老鼠必须进洞,那么就把它的代价赋为\(-inf\)。
部分问题的特殊性质可以保证复杂度,其他情况下作为一个暴力算法还是很优秀的。

上一篇:gym-100548G-回文树


下一篇:[luogu1131][ZJOI2007]时态同步