用费用流解释 雪灾与外卖 + 征服世界

feecle6418 · 2022-01-22 12:03:12 · 个人记录

网上题解说得云里雾里，特别是雪灾与外卖，几乎没有直白面对“这到底是模拟什么费用流图上的费用流？”。

其实要解释贪心做法，费用流图并不 trivial，而且并不是简单的二分图，也不是直接用横坐标建图。

我们需要拆点。

由于 征服世界 完全包含 雪灾与外卖（只是没有洞的权值 w，但不影响建图），我们就只讲征服世界了。

以下用 最小费用循环流 模型来解释这题。省略图中容量，不是重点。

首先你需要知道这题先把每个点都和 inf 配上了，之后剩下的工作只有消负环。以下只说怎么消负环的。

• 把每个点拆成 in,out。in 向 out 连费用为 -2\times 深度 的边。
• 从 x 的 in 向 x 的所有祖先 u 的 in 连费用为 0 的边。
• 从 x 的 out 向 x 的所有后代 u 的 out 连费用为 0 的边。

考虑 x,y 和某个公共祖先 u 之间发生的情况可以发现所有贡献都是对的，反悔的价值都是对的。

提几个问题供读者思考

1. 征服世界里面，x 点合并上来的两个堆分别有什么意义？（答案 https://www.luogu.com.cn/paste/c4dgcuim ）
2. 尝试用这个模型解释下面 雪灾与外卖 代码里面每一个语句（包括这些代价分别代表什么流，为什么只有这些流而没有其它流等）。（答案略，不懂可以问我）

void Ins2(int id){
    int s=0;
    while(q1.size()&&C[id]&&q1.top().val+Y[id]+W[id]<0){
        auto x=q1.top();
        q1.pop();
        int u=min(x.cnt,C[id]);
        ans+=1ll*u*(Y[id]+W[id]+x.val),C[id]-=u,s+=u;
        q2.push({-2*Y[id]-x.val,u});
        if(u<x.cnt)q1.push({x.val,x.cnt-u});
    }
    if(s)q1.push({-Y[id]-W[id],s});
    if(C[id])q2.push({-Y[id]+W[id],C[id]});
}