费用流

Vision271 · 2022-12-09 09:43:29 · 个人记录

SSP（Successive Shortest Path，连续最短路）算法

• 国内好像比较喜欢把这个叫 SPFA（毕竟国内好像很少见 Primal-Dual 原始对偶+Dijk 的外层）实现的 EK/Dinic/...？

• SSP 算法可以求出无负费用环网络的最小费用最大流。

• 实现原理：每次寻找费用最小的增广路，若有则增广之，没有则结束。

• 时间复杂度：

  • 事实上可以构造 m=n^2,f=2^\frac{n}{2} 的网络，使得 SSP 算法的复杂度达到 O(n^32^\frac{n}{2})（这里认为内层算法为 Bellman-Ford，x=nm），故该算法是伪多项式时间的。

• 这里我们做一个基于 Dinic-SPFA 的实现，即用 SPFA 代替 bfs 求出 dis(S,u) 来分层，内层 dfs 不变。

• 需要指出的是，这里的 Dinic 和原本的 Dinic 有本质性的不同：可能会有零费用环，图不再是分层图。这代表着 dfs 的逻辑得做一定的修改，且原本用于支撑复杂度的结论不再成立。

• 具体来说，我们在 dfs 时记录一个 vis（下面的实现直接复用了 spfa 的 in），表示某个点是否在 dfs 栈内，不允许成环。

• 从而当前弧优化不再有效：想要找到全部费用为 dis(S,T) 的增广路，我们每访问一个点，都得把它的所有出边遍历一遍。

  • 在原本的 Dinic 中，如果我们走过这条边，要么是根本不可行（不是相邻层），要么是这条边或它指向的点的流量用完了。

    • 这里所谓点的流量指的是从某个点出发能推到 T 的最大流量。

  • 然而现在还有可能是因为这是一个环，于是我们略过了这条边。

    • 考虑一个零环上的点 u,v,w，首先 u\to v\to w 于是 w 认为不能走向 u，于是当前弧把 w\to u 走过，以后如果还有别的什么点尝试扩展一条 S\to \dots\to w \to u \to \dots\to T 的增广路，就不可行了。(25.9.12 upd：这在说啥？按下面的实现，这种情况下 w,u 都 in 了，根本不可能被二次访问，遑论扩展增广路)

    • 这是一个例子，其中 u=2,v=3,w=4，dfs 时先走编号小的节点：

    • 确实，能搜出来 S\to 2\to 3\to 4，且增广路 S\to 5\to 4\to 2\to 3\to T 存在，说明这些路径中的所有边都有容量，进而增广路 S\to 2\to 3\to T 存在。

    • 但可能 S\to 2 是增广路 S\to 2\to 3\to T 的唯一瓶颈边，于是它至少在本轮 dfs 中把增广路 S\to 5\to 4\to 2\to 3\to T 卡掉了。

    • 多轮情况下能不能反复把一条增广路卡住，进而使每次 spfa 的结果都一样，进而这一条增广路导致死循环，应当是不能的：设导致死循环的增广路为 P，其中被当前弧 ban 掉的边为 s\to t，则 S\rightsquigarrow t 和 t\rightsquigarrow T 的“半增广路”都是存在的，于是能拼出来一条增广路。

    • 这实质上代表着，在有增广路的前提下，每次 dfs 至少单路增广，故不会死循环。但由于历史遗留问题，我们舍弃了这种实现。

  • 故当前弧优化失去效力，或原有的结论 2 不再成立，二者必居其一。

• 如果流量没推完就标记 dep=0 的优化也不能用了，理由显然，有可能是因为零环才没推完。

• 还有另一个实现细节：是否在退栈的时候取消标记。但我怀疑取消的实现会被卡，因为一般图的 dfs 显然不是多项式时间，取消...啧，危险的实现方式。

• 由于历史遗留问题，我们使用无当前弧优化+退栈不取消标记的实现方式。

const ll inf=4557430888798830399ll;
ll dis[maxp];
bool in[maxp];
il bool spfa(){
    memset(dis+1,63,sizeof(ll)*tot);
    static int q[maxp<<6],hd,tl;
    dis[S]=0,q[hd=tl=1]=S,in[S]=1;
    static int now; static ll res;
    while(hd<=tl){
        now=q[hd++],in[now]=0;
        for(int i=ehd[now];i;i=e[i].nxt)
            if(e[i].c){
                res=dis[now]+e[i].l;
                if(dis[e[i].to]>res){
                    dis[e[i].to]=res;
                    if(!in[e[i].to]) q[++tl]=e[i].to,in[e[i].to]=1;
                }
            }
    }
    return dis[T]<inf;
}

il ll dfs(int now,ll fl){
    if(now==T) return fl;
    ll rest=fl,used; in[now]=1;
    for(int i=ehd[now];i;i=e[i].nxt)
        if(e[i].c && !in[e[i].to] && dis[e[i].to]==dis[now]+e[i].l){
            used=dfs(e[i].to,mymin(rest,e[i].c));
            e[i].c-=used,e[i^1].c+=used;
            rest-=used; if(!rest) break;
        }
    return fl-rest;
}

il pair<ll,ll> dinic(){
    static pair<ll,ll> ret;
    static ll res; ret=m_p(0ll,0ll);
    while(spfa()){
        while((res=dfs(S,inf))){
            memset(in+1,0,sizeof(bool)*tot);
            ret.fir+=res;
            ret.sec+=dis[T]*res;
        }
        memset(in+1,0,sizeof(bool)*tot);
    }
    return ret;
}

• 同样，给出较为特殊的存边方式。反边的费用恰为正边费用的相反数，即撤销所付的代价。

struct edge{
    int to,nxt; ll c,l;
    edge(){}
    edge(int _to,int _nxt,ll _c,ll _l){to=_to,nxt=_nxt,c=_c,l=_l;}
}e[maxm<<1];
int etot=1,ehd[maxp];
il void addedge(int s,int t,ll c,ll l){
    e[++etot]=edge(t,ehd[s],c,l),ehd[s]=etot;
    e[++etot]=edge(s,ehd[t],0,-l),ehd[t]=etot;
    return;
}

• upd：还有一种非常怪的做法...即，同时使用 dis 和 dep 分层，这里的 dep 是最短路转移来源的 dep+1。优点是不会有 0 环，缺点...可能 SPFA 次数很多。不过目前来看，似乎常数比我这个写法优...

其他费用流算法

• 还没学。只知道至少可以做到弱多项式时间。这里放一下以后要学的博客的链接：

• [教程]网络流详解: 从入门到放弃-rvalue 这篇文章给出了一种消圈算法求最小费用最大流的思路，但没细讲。O(nm^2\log n)，但应当指出的是找负环时 spfa 的 km 中的 k 很容易很大，故常数极差，随机数据下不一定跑得赢 SSP。

• 基于 Capacity Scaling 的弱多项式复杂度最小费用流算法-ouuan 这篇文章给出了一种，额，更高效的弱多项式时间算法，似乎是基于 容量缩放增广路算法（Capacity scaling algorithm，这里采用《最小割模型在信息学竞赛中的应用》-胡伯涛中的翻译）。O(m^2\log (\max{c})\log m)，其中 \max{c} 为最大容量的路径的容量，主要缺点是实现过于复杂。

• 有空学一学吧。

例题

P1251 餐巾计划问题

• 题意略。首先容易看出是费用流，因为有两个信息需要维护（餐巾数量和所花钱数）。

• 那么容易想到把餐巾数量作为流量，钱数是费用。考虑建图，i\to T(req_i,0)，这是显然的。

• 注意到延后送洗意义不大。考虑强制当天送洗，然后在任意时刻取用；类似地，想到在第一天买完，任意时刻取用。于是 S\to 1(+\infty,buy),i\to i+1(+\infty,0),i\to i+t_0...?。

• 注意到好像有问题。我们在第 i 天用掉的餐巾已经推流到 T 了，而我们的送洗操作在某种意义上其实是“流量回收”，于是...嗯，从 i 向洗好的时间连边是不对的，那其实代表的是把干净的餐巾送洗了。

• 转而考虑从 S 把洗好的毛巾推流出去，对每一天用完的毛巾开一个点 wash_i，S\to wash_i(req_i,0),wash_i\to i+t_x(req_i,c_x)。

• 好像对了。我们不管费用流的复杂度嗷。

P2604 [ZJOI2010] 网络扩容

• 题意略。挺板的。

• 先跑最大流，再把最大流的残量网络拉过来跑费用流就好。

• 不建议直接在残量网络上动手，毕竟费用流的复杂度...我宁可重构图，这样可以少跑一次费用流。

• 哦我可以按费用流建图然后假装没有费用跑一次最大流。妙！

P4016 负载平衡问题

• 题意略。

• 简单分析之后发现大概可以贪。

  • 首先不可能成环，否则不优。

  • 于是如果所有边都用了，应该是运货的时候 S\to T 的两边都走了（想象 S 是一个溢出货物中心，T 是不足中心）。

  • 总有办法调整使得其至少有一条边不被使用。

  • 故直接破环成链，然后从左向右考虑，有冗余量则先与左边的需求量消一下，然后付出对应代价并向下一个点发送对应冗余量，反之亦然，O(n^2)。

• 但是！学网络流就是为了艹过去！直接暴力建图，S\to i(num_i,0),i\to i+1/i-1(einf,1),i\to T(ave,0)。

• 完事，复杂度不算了。

P4015 运输问题

• 题意略。板题。无趣。

P4014 分配问题

• 题意略。就是上一题改一改读入...

P4013 数字梯形问题

• 题意略。

• 第一问拆点。第二问把点内部的流量改成 +\infty，注意起始点不能这样。第三问可以把边的流量也改成 +\infty，当然我们知道这其实 DP 就够了，不过我图省事跑了三遍 SSP。

P4012 深海机器人问题

• 题意略...体感上就是费用流板子，没什么好说的。

P3358 最长 k 可重区间集问题

• 题意略。本题的建图非常妙。

P3357 最长 k 可重线段集问题

• 题意略。设法将上一题的解法推广，发现有问题，即竖线之间可能彼此冲突。

• 扩域！将竖线的 L,R 扔到 2L,2R+1，其他的则是 2L+1,2R。注意开线段的左右都是开的，所以以 xn 结尾的非竖线和 l:x=xn 并无交点，于是这让竖线互相冲突，非竖线互相冲突（当然也会和被包含的竖线冲突），遂得解。

P2770 航空路线问题

• 题意略。本来想不清楚，但从可重区间那道题学到一点建图方法，于是...

• 首先做一个和危桥类似的转化，来回相当于过去两遍。

• 然后将城市拆点，注意 1,n 两个的内部流量应该为 2，但只有第 1 个流量有费用，所以应该建 (1,-1) 和 (1,0) 两条。同理，边应该也是 (2,0) 的，以防 1\to n\to 1 这种奇葩情况。

• 然后谈谈怎么构造方案...虽然可以说容易构造，但是说实话这道题的方案挺恶心的。我的办法是：一路 dfs 到 n，期间不断输出正边（先输出正边再进儿子，前序），到达后标 flag=1 然后退栈，后面的 dfs 改成后序（儿子退出来了再输出儿子到我的反边）。

• 急了？先别急，后面的方案有的是让人急的。

P3356 火星探险问题

• 题意略。它来了，它来了，最恶心的方案它来了！

• 显然是板子，嗯哼？但是怎么输出方案？没有方案的话也就是个拆点的深海机器人而已。

• 把所有有流量的正边拆下来（我实际上没有拆就是在残量网络上硬跑的），记录对应流量，每次从起点出发搜一条路径出来。

• 可以证明这一定是对的，毕竟局部来看，流量平衡；全局来看，不管我们怎么走，大不了说这是等效退流。

P4009 汽车加油行驶问题

• 题意略。这道题被我开除了，太丢人了，堂堂网络流紫题竟然就是个 \text{P4568 [JLOI2011] 飞行路线} 的不分层版本。

• 分层图拆点最短路，当然这里有环没法一层一层转移就是了。