网络流

mRXxy0o0 · 2023-11-21 22:01:07 · 个人记录

1.最大流

定义

自行意会。

原理

找一条 S-T 的正权路径，给里面加流量。

显然是错的，但是可以再存反边，类似一种反悔的思想。其最大流量为 0。

此处的边权皆为空余流量。

实现

EK/FF

用 DFS、BFS 打暴力。

ISAP

预处理每个点到 T 的反图最短路（实际无必要），以此分层，DFS 分配新流量。

有一些显然的优化。GAP 断层优化、当前弧优化。还有层数较小时，可以玄学少跑几次。

namespace flow{
    const int N=1e5+10,M=2e5+10;
    int h[N],ne[M],e[M],w[M],idx=1,S,T,tot,cnt[N],dis[N],cur[N];
    inline void addE(int u,int v,int x){
        ne[++idx]=h[u],h[u]=idx,e[idx]=v,w[idx]=x;
    }
    inline void add(int u,int v,int x){
        addE(u,v,x),addE(v,u,0);
    }
    inline int dfs(int u,int sum){
        if(u==T) return sum;
        int ss=0;
        for(int &i=cur[u];i;i=ne[i]){
            int v=e[i];
            if(w[i]<=0||dis[u]!=dis[v]+1) continue;
            int tmp=dfs(v,min(w[i],sum-ss));
            ss+=tmp,w[i]-=tmp,w[i^1]+=tmp;
            if(sum==ss||dis[S]>=tot) return ss;
        }
        if(!--cnt[dis[u]]) dis[S]=tot;
        ++cnt[++dis[u]];
        cur[u]=h[u];
        return ss;
    }
    inline int work(){
        int res=0;
        for(int i=1;i<=tot;++i) cur[i]=h[i];
        while(dis[S]<tot) res+=dfs(S,inf);
        return res;
    }
}
using flow::S;
using flow::T;
using flow::tot;
using flow::add;
using flow::work;

注意

• 链式前向星建图正反边一定要相邻建。

• idx 初值要是奇数。

• 网格图用 id[][] 数组时，一定要考虑是不是赋过值的。可以分成多个部分，不要太压行。

• 数组大小。

建模

• 神奇猜结论。

• 结合 DP 状态。

• 用点来分流。

• 图上分层拆点跑残量网络，直至流量大于等于某值（EK/dinic 更优）。

• 转最小割，跑 DP。

2.最小割

定义

分成包含 S 和 T 的两部分点，使 S 部到 T 部的边流量和最小。

原理

值等于最大流，考虑非最大流就会有未填满的路径。

实现

同最大流。

建模

• 核心，不能有通路。

• 网格图染色（2或4），建图。但不能一见网格图就一定是。

• 串联=或；并联=且。

• 点权转边权。

• 拆点、限流。

• 每个点分类型，有代价。

• 一组在一起有额外代价（建模同下）。

• 每个点分类型，有贡献。
• 一组在一起有额外贡献（建模如嫖来的图，C_i 在就意味着它所连的组必须没有连向 T 的）。

• 当在同一个集合有代价时，可以选择一类路径反向、交换集合边权。

• 找边数最小最小割，增量法（乘）。

最大权闭合子图

定义

没有向外出边的点集，使其点权和最大。

原理

单点涂白 c!bh_{i,j}ws_{i,j}+cbs_{i,j}!wh_{i,j}+\infty(bh_{i,j}+)

最小割二元系数一定要是负，所以布尔表达式一定要二元且一个正一个反。上式中原始式子有三项的讨论干掉，同正反的选一些取反。

bh，ws 取反

比如说两个物品四种分配方式，可以建模的前提是 W_{00}+W_{11}\le W_{01}+W_{10}，原因可用 bool 表达式证明。

3.费用流

定义

最值费用最大流。

原理

贪心，优先增广最短路（ISAP 当中最短路带权）。

实现

SPFA 求最短路（有负环，只走有流量的边），最短路上增广。

• 多路增广。

可以类似 SAP，但是无优化。

namespace mincost{
    const int N=1e5+10,M=1e6+10;
    int S,T,tot,dis[N],h[N],ne[M],e[M],w1[M],w2[M],idx=1,q[N],hh,tt,pre[N],flow[N];
    bool vis[N];
    inline void addE(int u,int v,int x1,int x2){
        ne[++idx]=h[u],h[u]=idx,e[idx]=v,w1[idx]=x1,w2[idx]=x2;
    }
    inline void add(int u,int v,int x1,int x2){
        addE(u,v,x1,x2),addE(v,u,0,-x2);
    }
    inline bool spfa(){
        memset(dis,-0x3f,sizeof(int)*(tot+5));
        memset(flow,0x3f,sizeof(int)*(tot+5));
        memset(vis,0,sizeof(bool)*(tot+5));
        hh=0,tt=1;
        q[0]=S;
        dis[S]=0;
        while(hh!=tt){
            int u=q[hh++];
            if(hh==N) hh=0;
            vis[u]=0;
            for(int i=h[u];i;i=ne[i]){
                int v=e[i],tmp=dis[u]+w2[i];
                if(w1[i]>0&&dis[v]<tmp){
                    dis[v]=tmp;
                    pre[v]=i^1;
                    flow[v]=min(flow[u],w1[i]);
                    if(!vis[v]){
                        vis[v]=1;
                        q[tt++]=v;
                        if(tt==N) tt=0;
                    }
                }
            }
        }
        return dis[T]>-inf;
    }
    inline void work(){
        int res=0,sum=0;
        while(spfa()){
            sum+=flow[T];
            res+=flow[T]*dis[T];
            for(int i=T;i!=S;i=e[pre[i]]){
                w1[pre[i]]+=flow[T];
                w1[pre[i]^1]-=flow[T];
            }
        }
        printf("%d %d",sum,res);
    }
}
using mincost::S;
using mincost::T;
using mincost::tot;
using mincost::add;
using mincost::work;

细节

静态数组作队列，一定要判越界，循环使用内存。

memset 最后尽量用 sizeof，不要自己算，可以把点数开精确一点。（悲

可以动态加边。

Primal-Dual

考虑 SPFA 很慢，我们使用 dij，类似 Johnson 全源最短路，考虑最初用 SPFA 给每个点跑势能（最短路），然后令 (u,v,w)\Rightarrow (u,v,w+h_u-h_v\ge0)，这样全图无负权。

正确性考虑势能最终都被抵消掉了。但是增广后图会变化，只需要 h'=h+dis。证明也差不多。

然后某些题可以多路增广，就再套一个dinic（就是先BFS分层，再跑SAP）、sap状物。

namespace mincost{
    const int N=1e5+10,M=1e6+10;
    int S,T,tot,dis[N],h[N],ne[M],e[M],w1[M],w2[M],idx=1,D[N],q[N],hh,tt,cur[N];
    bool vis[N];
    inline void addE(int u,int v,int x1,int x2){
        ne[++idx]=h[u],h[u]=idx,e[idx]=v,w1[idx]=x1,w2[idx]=x2;
    }
    inline void add(int u,int v,int x1,int x2){
        addE(u,v,x1,x2),addE(v,u,0,-x2);
    }
    inline void spfa(){
        memset(D,0x3f,sizeof(int)*(tot+5));
        memset(vis,0,sizeof(bool)*(tot+5));
        hh=0,tt=1;
        q[0]=S;
        D[S]=0;
        while(hh!=tt){
            int u=q[hh++];
            if(hh==N) hh=0;
            vis[u]=0;
            for(int i=h[u];i;i=ne[i]){
                int v=e[i],tmp=D[u]+w2[i];
                if(w1[i]&&D[v]>tmp){
                    D[v]=tmp;
                    if(!vis[v]){
                        vis[v]=1;
                        q[tt++]=v;
                        if(tt==N) tt=0;
                    }
                }
            }
        }
    }
    inline bool dij(){
        priority_queue<pii,vector<pii>,greater<pii> >q;
        memset(vis,0,sizeof(bool)*(tot+5));
        memset(dis,0x3f,sizeof dis);
        q.push({dis[S]=0,S});
        while(!q.empty()){
            int u=q.top().second;q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(int i=h[u];i;i=ne[i]){
                int v=e[i],t=dis[u]+w2[i]+D[u]-D[v];
                if(w1[i]>0&&dis[v]>t) q.push({dis[v]=t,v});
            }
        }
        for(int i=1;i<=tot;++i) D[i]+=dis[i];
        return D[T]<0;
    }
    int dep[N];
    inline bool bfs(){
        memset(dep,0,sizeof(int)*(tot+5));
        memcpy(cur,h,sizeof(int)*(tot+5));
        dep[S]=1;
        q[hh=tt=0]=S;
        while(hh<=tt){
            int u=q[hh++];
            for(int i=h[u];i;i=ne[i]){
                int v=e[i];
                if(w1[i]>0&&D[v]==D[u]+w2[i]&&!dep[v]) dep[v]=dep[u]+1,q[++tt]=v;
            }
        }
        return dep[T];
    }
    inline int dfs(int u,int sum){
        if(u==T) return sum;
        int ss=0;
        for(int &i=cur[u];i;i=ne[i]){
            int v=e[i];
            if(w1[i]<=0||dep[v]!=dep[u]+1||D[v]!=D[u]+w2[i]) continue;
            int t=dfs(v,min(sum-ss,w1[i]));
            ss+=t,w1[i]-=t,w1[i^1]+=t;
            if(sum==ss) return ss;
        }
        return ss;
    }
    inline void work(){
        spfa();
        int res=0;
        while(dij()){
            int val=-D[T];
            while(bfs()) for(int i=dfs(S,inf);i;--i) ans[++res]=val;
        }
    }
}
using mincost::S;
using mincost::T;
using mincost::tot;
using mincost::add;
using mincost::work;

建模

最大流满足一个限制，费用再求另一个最值。

拆点定流

还是拆点，但是不好限制每一个点刚刚好有给定的流量。考虑直接让拆出来的 2n 个点凭空获得流（当然，有代价），再通过题目条件，把流分出去，这里的“分”具有偏序关系，同一层的点也可以视情况有偏序关系。

另一道

区间满足上下界限制

有上下界，流入上界，到一个点分出一些，使不从 i\rightarrow i+1 的流 \in[l,r]。

拆点定向

网格图，只有连成环的拐弯才有权值。染色，分类。一个点分上下方向和左右方向，连两条边，一条有权，一条无权，最终减去一倍权和。相邻对应连。

• 总的减去一部分。预先设置一些状态，再调整。

• 拆绝对值。

4.上下界网络流

定义

每个边的流量有上下界。

可行流

定义

问有没有解。

最大/小流

定义

在满足限制下的最值。

实现

namespace udflow{
    const int N=1e5+10,M=2e6+10;
    int S,T,S1,T1,S2,T2,tot,h[N],ne[M],e[M],w[M],idx=1,cur[N],cnt[N],dis[N],exfl,du[N];
    inline void addE(int u,int v,int x){
        ne[++idx]=h[u],h[u]=idx,e[idx]=v,w[idx]=x;
    }
    inline void add(int u,int v,int l,int r){
        du[v]+=l,du[u]-=l;
        addE(u,v,r-l),addE(v,u,0);
    }
    inline int dfs(int u,int sum){
        if(u==T2) return sum;
        int ss=0;
        for(int &i=cur[u];i;i=ne[i]){
            int v=e[i];
            if(w[i]<=0||dis[u]!=dis[v]+1) continue;
            int tmp=dfs(v,min(w[i],sum-ss));
            ss+=tmp,w[i]-=tmp,w[i^1]+=tmp;
            if(sum==ss||dis[S2]>=tot) return ss;
        }
        if(!--cnt[dis[u]]) dis[S2]=tot;
        ++cnt[++dis[u]];
        cur[u]=h[u];
        return ss;
    }
    inline void init(){
        memset(dis,0,sizeof dis);
        memset(cnt,0,sizeof cnt);
    }
    inline int work(){
        addE(T,S,inf),addE(S,T,0);
        int bg=idx;
        for(int i=1;i<=tot;++i){
            if(du[i]>0) addE(S1,i,du[i]),addE(i,S1,0),exfl+=du[i];
            if(du[i]<0) addE(i,T1,-du[i]),addE(T1,i,0);
        }
        for(int i=1;i<=tot;++i) cur[i]=h[i];
        int res=0;
        S2=S1,T2=T1;
        while(dis[S2]<tot) res+=dfs(S2,inf);
        if(res!=exfl) return -1;
        init();
        for(int i=1;i<=tot;++i) cur[i]=h[i];
        S2=S,T2=T;
        res=w[bg];
        w[bg]=w[bg-1]=0;
        while(dis[S2]<tot) res+=dfs(S2,inf);
        return res;
    }
}
using udflow::S;
using udflow::T;
using udflow::S1;
using udflow::T1;
using udflow::tot;
using udflow::add;
using udflow::work;

费用流

定义

区分一下最值费用最大流和单纯的费用流。

后者在增广的 dis 不优后就可以退出了。

实现

namespace udflow{
    const int N=1e5+10,M=2e6+10;
    int S,T,S1,T1,S2,T2,tot,h[N],ne[M],e[M],w1[M],w2[M],idx=1,q[N],hh,tt,sum,flow[N],pre[N],dis[N],du[N];
    bool vis[N];
    inline void addE(int u,int v,int x1,int x2){
        ne[++idx]=h[u],h[u]=idx,e[idx]=v,w1[idx]=x1,w2[idx]=x2;
    }
    inline void add(int u,int v,int l,int r,int x){
        sum+=l*x;
        du[v]+=l,du[u]-=l;
        addE(u,v,r-l,x),addE(v,u,0,-x);
    }
    inline bool spfa(){
        memset(dis,0x3f,sizeof dis);
        memset(flow,0x3f,sizeof flow);
        memset(vis,0,sizeof vis);
        hh=0,tt=1;
        q[0]=S2;
        dis[S2]=0;
        while(hh!=tt){
            int u=q[hh++];
            if(hh==N) hh=0;
            vis[u]=0;
            for(int i=h[u];i;i=ne[i]){
                int v=e[i],tmp=dis[u]+w2[i];
                if(w1[i]>0&&dis[v]>tmp){
                    dis[v]=tmp;
                    flow[v]=min(flow[u],w1[i]);
                    pre[v]=i^1;
                    if(!vis[v]){
                        vis[v]=1;
                        q[tt++]=v;
                        if(tt==N) tt=0;
                    }
                }
            }
        }
        return dis[T]<inf;
    }
    inline int work(){
        addE(T,S,inf,0),addE(S,T,0,0);
        for(int i=1;i<=tot;++i){
            if(du[i]>0) addE(S1,i,du[i],0),addE(i,S1,0,0);
            if(du[i]<0) addE(i,T1,-du[i],0),addE(T1,i,0,0);
        }
        int res=sum;
        S2=S1,T2=T1;
        while(spfa()){
            res+=dis[T2]*flow[T2];
            for(int i=T2;i!=S2;i=e[pre[i]]){
                w1[pre[i]]+=flow[T2];
                w1[pre[i]^1]-=flow[T2];
            }
        }
        return res;
    }
}
using udflow::S;
using udflow::T;
using udflow::S1;
using udflow::T1;
using udflow::tot;
using udflow::add;
using udflow::addE;
using udflow::work;