最大流与Dijkstra做费用流

0x00网络流简介

　　网络流G=(V, E)是一个有向图,其中每条边(u, v)均有一个非负的容量值,记为c(u, v)\geq0.如果(u, v)\notin E则可以规定c(u, v)=0.网络流中有两个特殊的顶点,即源点S和汇点T,源点可以提供无限的流量,而汇点可以接受无限的流量.

　　与网络流相关的一个概念是流.设S为网络的源点,T为汇点，那么G的流是一个函数f:V×V →R,满足以下性质:

　　容量限制：\forall u,v∈V，满足f(u, v) \leq c(u, v);

　　反对称性：\forall u,v∈V，满足f(u, v) = - f(v, u);

　　流守恒性：\forall u∈V-{S, T}，满足\sum_{v∈V}f(u,v)=0。

　　流f的值定义为

|f|=\sum_{v\in V}f(s,v)

　　而最大流就是值最大的流.

　　可以形象地理解为:源点是一个水库,汇点是一个用水量无限的用户,其它点是中转站,而边就是连接三者的水管.一个流就是一种合法的输水方案(每条水管运送水量在其容量之内,除了源点不会莫名其妙地出现水),它的值就是用户接受到的水量,而最大流就是用户接受水量最大的输水方案.

　　残留网络是由可以容纳更多流的边组成的,即如果G中的一条边没有满流,那么它就是残留网络G_f中的一条边.

　　一条增广路则是指G_f中从S到T的一条路径.

0x01最大流算法:以Dinic算法为例

以下定义:

$w[i][j]$为连接$i,j$的边的边权 $c[i]$为边$i$的费用 $dis[i]$为起点到点$i$的距离 $S$为源点 $T$为汇点

Dinic算法大致步骤:

1.用BFS给图标号,每个点的标号为到源点的最近距离(只走剩余容量大于0的边).

2.若BFS无法到达汇点则算法结束.

3.DFS一遍找出一条从源点到汇点的增广路,DFS时只走标号比当前点大1的点.

4.若没有这样的路径则返回1,否则将此路计入答案,并更新反向边,重复3.

反向边的概念:

假设有这样一个图(边上的数字代表其容量)

现在有一条2到5的路径

对于路径上每一条边(u,v),建立一条(v,u),容量为经过(u,v)的流量的边(图中绿色边)

假设又有一条6到1的边

那么最终的图是这样的(每条边上:(容量,流量))

例子:

BFS标号

DFS

更新反向边

由于无路可走,再BFS并DFS

更新反向边

无路可走,退出

最终:

PS:每条边上(容量,流量) Code(P3376)

#define out(i,a,now) for(int i=a.be[now],to=a.v[i];i;i=a.ne[i],to=a.v[i])
#define fo(i,a,b) for(i=a;i<=b;i++)
struct adj_list
{
    LL be[maxn],ne[maxm<<2],v[maxm<<2],w[maxm<<2],cnt;
    void init()
    {
        qk(be); cnt=1;
    }
    void add(LL x,LL y,LL z)
    {
        v[++cnt]=y;
        ne[cnt]=be[x];
        w[cnt]=z;
        be[x]=cnt;
    }
}v;
LL bfs()//标号
{
    queue<LL> q;
    q.push(t);
    qk(id);
    id[t]=1;
    while (!q.empty())
    {
        LL now=q.front();
        q.pop();
        if (now==s) break;
        out(i,v,now)
        if (v.w[i^1] && !id[to])
        {
            id[to]=id[now]+1;
            q.push(to);
        }
    }
    return id[s];//判断是否有可行流
}
LL dfs(LL now,LL flow)//寻找可行流
{
    if (now==t) return flow;
    LL miflow;
    out(i,v,now)
    {
        LL wei=v.w[i];
        if (wei && id[to]==id[now]-1)
        {
            miflow=dfs(to,min(flow,wei));
            if (miflow)
            {
                v.w[i]-=miflow;
                v.w[i^1]+=miflow;//增加反向边流量
                return miflow;
            }
        }
    }
    return 0;
}
LL dinic()
{
    LL res=0;
    while (bfs())
    {
        LL temp;
        while (temp=dfs(s,LLONG_MAX>>1))
            res+=temp;
    }
    return res;
}
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    LL i;
    LL x,y,z;
    v.init();
    fo(i,1,m)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        v.add(x,y,z);
        v.add(y,x,0);
    }
    LL ans=dinic();
    printf("%lld",ans);
}

0x02最小费用最大流算法

　　现在你需要为流经一条边i的单位流量支付费用c[i],其实只需将最大流算法中的DFS改为求最短路,找到一条从源点到汇点每条边费用之和最小的路并更新答案.

　　鉴于现在SPFA人人喊打,以下给出一种使用dijkstra算法的方法.

　　由于费用可能为负数,普通的dijkstra算法无法实现.因此我们考虑对原图做一次SPFA求出源点到每个点的最短路,之后我们为每个点i赋点权h[i]为dis[i],并视每条连接u,v的边i的边权w'[i]为w[i]+h[u]-h[v],由于对于任意两点u,v,有h[u]-h[v]>=w[u][v],所以w'[i]>=0,这样一来新图上的dis'[i]就等于dis[i]+h[S]-h[i](对于路径上除起点和终点以外的点i,其入边的-h[i]与出边的+h[i]抵消),由于每次跑最短路时h[i]都是不变的,所以求出了dis'[i]也就求出了dis[i](dis[i]=dis'[i]-h[S]+h[i],其实很显然h[S]=0)

　　但是跑完之后需要加入反向边,原来的h[i]可能会不适用,所以我们需要更新h[i] 对于最短路上每一条连接(u,v)的边,显然有dis'[u]+w'[u][v]=dis'[v] 从而

dis'[u]+h[u]-h[v]+w[u][v]=dis'[v] (dis'[u]+h[u])-(dis'[v]+h[v])+w[u][v]=0 ∵w[u][v]=-w[v][u] ∴(dis'[v]+h[v])-(dis'[u]+h[u])+w[v][u]=0

所以我们只要对于每个点i将h[i]加上dis'[i]即可.

由于

dis'[i]+h[i]=dis[i]+h[S]-h[i]+h[i]=dis[i]+h[S]

h[S]又是一个常量(就是0) 所以h[i]还是一开始我们所希望的dis[i],对于每个点i将h[i]加上dis'[i]不会破坏每条边边权不为负的特性.

Code(P3381)

#define out(i,a,now) for(int i=a.be[now],to=a.v[i];~i;i=a.ne[i],to=a.v[i])
#define fo(i,a,b) for(i=a;i<=b;i++)
struct adj_list
{
    LL be[maxn],ne[maxm<<4],v[maxm<<4],w[maxm<<4],c[maxm<<4],cnt;
    void init()
    {
        memset(be,-1,sizeof(be));
        cnt=0;
    }
    void add(LL pre,LL nxt,LL wei,LL cost)
    {
        v[cnt]=nxt;
        ne[cnt]=be[pre];
        be[pre]=cnt;
        w[cnt]=wei;
        c[cnt]=cost;
        ++cnt;
    }
};
struct NetWork
{
    adj_list v;
    LL dis[maxn],h[maxn],pre_node[maxn],pre_edge[maxn],inque[maxn];
    void SPFA(LL be,LL en)
    {
        queue<LL> q;
        qk(inque);
        LL i;
        fo(i,1,n) h[i]=LLONG_MAX>>1;
        h[be]=0; inque[be]=1;
        q.push(be);
        while (!q.empty())
        {
            LL now=q.front();
            q.pop();
            out(i,v,now)
            if (h[now]+v.c[i]<h[to] && v.w[i])
            {
                h[to]=h[now]+v.c[i];
                if (!inque[to])
                {
                    q.push(to);
                    inque[to]=1;
                }
            }
            inque[now]=0;
        }
    }
    void MCMF(LL s,LL t,LL &flow,LL &cost)
    {
        flow=cost=0;
        SPFA(s,t);//用一次SPFA更新h数组
        while (1)
        {
            pre_node[s]=pre_edge[s]=-1;//开始堆优化dijkstra算法
            LL i;
            fo(i,1,n) dis[i]=LLONG_MAX>>1;
            dis[s]=0;
            priority_queue<Pair,vector<Pair>,greater<Pair> > pq;
            pq.push(mp(0,s));
            while(!pq.empty())
            {
                Pair now=pq.top();
                pq.pop();
                if (now.first!=dis[now.second]) continue;
                if (now.second==t) break;
                out(i,v,now.second)
                {
                    LL len=v.c[i]+h[now.second]-h[to];
                    if (v.w[i] && dis[now.second]+len<dis[to])
                    {
                        dis[to]=dis[now.second]+len;
                        pq.push(mp(dis[to],to));
                        pre_node[to]=now.second;//记录从哪个点来
                        pre_edge[to]=i;//记录从哪条边来
                    }
                }
            }
            if (dis[t]>=(LLONG_MAX>>1)) break;
            LL miflow=LLONG_MAX>>1;
            for(i=t;i!=s;i=pre_node[i])
                cmin(miflow,v.w[pre_edge[i]]);//找到路径上流量最小值
            for(i=t;~i;i=pre_node[i])
            {
                v.w[pre_edge[i]]-=miflow;
                v.w[pre_edge[i]^1]+=miflow;//更新反向边
            }
            flow+=miflow;
            cost+=miflow*(h[t]+dis[t]);
            fo(i,1,n) h[i]=min(h[i]+dis[i],LLONG_MAX>>1);//更新h数组
        }
    }
    void sol()
    {
        v.init();
        LL i,x,y,z,w;
        scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
        fo(i,1,m)
        {
            scanf("%lld%lld%lld%lld",&x,&y,&z,&w);
            v.add(x,y,z,w);
            v.add(y,x,0,-w);
        }
        LL flow,cost;
        MCMF(s,t,flow,cost);
        printf("%lld %lld",flow,cost);
    }
}solver;
int main()
{
    solver.sol();
    return 0;
}

0x03最小割最大流定理

　　G的一个割把点集V分为两部分,其中源点S属于其中一部分,汇点T属于另外一部分.割是G的边集E的一个子集,每条边的两个端点分别属于不同的点集.割的容量定义为割的每条边的容量和,最小割就是容量最小的一个割.

　　例子:

　　

　　黄色的边就是一个割

　　介绍一下网络流中最重要的定理之一------最小割最大流定理:

　　如果f是G中一个流,则以下条件是等价的:

　　1.f是G的一个最大流

　　2.残留网络G_f不包含增广路

　　3.存在一个割,|f|等于其容量

　　那么如何借此求出最小割呢?我们看可以先求出最大流,以S为起点在残留网络上DFS,搜索到的点就是包含S的一部分,剩余的则是另一部分,而最小割即是连接两部分的所有边.

0x04典型例题

1.飞行员配对方案问题(P2756)

　　一个二分图最大匹配问题,源点向所有外籍飞行员连容量为1的边,外籍飞行员向可以配对的英国飞行员连容量为1的边,英国飞行员向汇点连容量为1的边,网络最大流即是答案,若外籍飞行员连向英国飞行员的边满流,说明这一对被选中.

　　Code

2.太空飞行计划问题(P2762)

　　一个最大权闭合图问题,详细说明可以见胡伯涛的《最小割模型在信息学竞赛中的应用》.

　　简要说一下方法:源点向实验连容量为利润的边,实验向所需器材连容量为无穷大的边,器材向汇点连容量为花费的边,所有实验利润之和减去网络最小割的容量即是答案,方案可以按照上文方法输出.

　　Code

3.最小路径覆盖问题(P2764)

　　寻找最小路径条数等价于为尽可能多的点找到后继,于是就可以用一种类似于二分图匹配的方法求解.将点i拆为i_1,i_2,源点向所有i_1连容量为1的边,所有i_2向汇点连容量为1的边,若原图上有边(u,v),则u_1向v_2连容量为1的边.答案为总点数减去网络最大流(网络最大流就是找到了后继的点数),若u_1向v_2的边满流,说明路径上v是u的后继.

　　Code