听课笔记 - 2026 重庆 - 04 网络流建模【Dinic】【Dilworth 定理】【上下界网络流】

ExFish · 2026-01-24 08:33:41 · 算法·理论

膜拜 orzGEOTCBRL。

定义见我自己的学习笔记。

增广路径与残量网络

考虑 FF 算法是每一次 dfs 在残量网络（建造反向边来返回）中找一条增广路流 1 流量复杂度为 \mathcal O(mf)。然后我们改良为 \mathcal O(n^2m) 的 EK，也就是每一次增广 \min 的容量，最多 n 次增广就结束，复杂度容易证明。

Dinic 复杂度分析

然后 Dinic 就是按照层次增广。也就是首先 bfs 按照 dep 分层。这个过程就是 \mathcal O(n) 的。然后是当前弧优化，你就发现一个点最多就走出边次，也就是一次增广就只有 \mathcal O(m)，总复杂度为 \mathcal O(nm)。但是注意有 n 层分层所以总复杂度为 \mathcal O(n^2m) 的。

虽然这看起来跟 EK 是一样的，但是你根本卡不满，所以一般可以当做为 n\sqrt{m} 之类的超级小时间复杂度呢。

最大流最小割定理

这个我在学习笔记里写过，但是直接是搬的 OI-wiki。也就是删除边让源点汇点不连通。你发现这个东西就相当于最大流。然后最小割是容易转化的。

P2057 善意的投票

考虑网络流建模。考虑建模二分图，赞成左侧，反对右侧。S 是连赞成，T 连反对，朋友连双向的容量为 1 的边。你发现割 S\to u 就是让 u 取反，v\to T 就是让 v 取反，u\to v 就是让两人叛变。所以这样就变成最小割模版。

::::success[code] 警示：开大点。注意 ll。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=305,M=9e4+10;
int tot=1, hd[N];
int n,m,a[N];
struct edges{ int to,nxt; ll w; } e[2*M];
void addedge(int u,int v,ll w){
    ++tot; e[tot]={v,hd[u],w};
    hd[u]=tot;
}
const ll inf=1e12;
ll now[N],dep[N];
queue<int>q;
int s,t;
bool bfs(){
    for(int i=0;i<=n+1;i++) dep[i]=inf;
    dep[s]=0; now[s]=hd[s];
    while(q.size()) q.pop();
    q.push(s);
    while(q.size()){
        int p=q.front(); q.pop();
        for(int i=hd[p];i>0;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0&&dep[v]==inf){
                q.push(v);
                now[v]=hd[v];
                dep[v]=dep[p]+1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
ll dfs(int p,ll flow){
    if(p==t) return flow;
    ll nowf=0,cost;
    for(int i=now[p];i>0&&flow>0;i=e[i].nxt){
        int v=e[i].to; now[p]=i;
        if(e[i].w>0&&(dep[v]==dep[p]+1)){
            cost=dfs(v,min(flow,e[i].w));
            if(!cost) dep[v]=inf;
            e[i].w-=cost, e[i^1].w+=cost;
            nowf +=cost, flow-=cost;
        }
    }
    return nowf;
}
ll maxflow(){
    ll ans=0;
    while(bfs()) ans+=dfs(s,inf);
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        addedge(u,v,1);
        addedge(v,u,0);
        addedge(v,u,1);
        addedge(u,v,0);
    }
    s=0, t=n+1;
    for(int i=1;i<=n;i++)
        if(a[i]) addedge(s,i,1), addedge(i,s,0);
        else addedge(i,t,1), addedge(t,i,0);
    cout<<maxflow();
    return 0;
}

::::

P1345 奶牛的电信

如何求最小割点？考虑转化一个点为一个入点和出点，所有原图上的边就没有容量限制，然后这个点的容量就是 1，这个就是最小割的板子了。

::::success[code] 注意边数数组大小。

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=1e5+10;
#define ll long long
int n,m,s,t;
int tot=1,hd[N];
struct edges{ int to,nxt; ll w; }e[2*M];
void addedge(int u,int v,ll w){ ++tot; e[tot]={v,hd[u],w}; hd[u]=tot; }
const ll inf=1e12;
ll now[N],dep[N];
queue<int>q;
bool bfs(){
    for(int i=0;i<500;i++) dep[i]=inf;
    dep[s]=0; now[s]=hd[s];
    while(q.size()) q.pop();
    q.push(s);
    while(q.size()){
        int p=q.front(); q.pop();
        for(int i=hd[p];i>0;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0&&dep[v]==inf){
                q.push(v);
                now[v]=hd[v];
                dep[v]=dep[p]+1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
ll dfs(int p,ll flow){
    if(p==t) return flow;
    ll cost,nowf=0;
    for(int i=now[p];i>0&&flow>0;i=e[i].nxt){
        int v=e[i].to; now[p]=i;
        if(e[i].w>0&&(dep[v]==dep[p]+1)){
            cost=dfs(v,min(flow,e[i].w));
            if(!cost) dep[v]=inf;
            e[i].w-=cost, e[i^1].w+=cost;
            nowf+=cost, flow-=cost;
        }
    }   
    return nowf;
}
ll maxflow(){
    ll ans=0;
    while(bfs()) ans+=dfs(s,inf);
    return ans;
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=n;i++)
        addedge(i,n+i,1),
        addedge(n+i,i,0);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        addedge(u+n,v,inf);
        addedge(v,u+n,0);
        addedge(v+n,u,inf);
        addedge(u,v+n,0);
    }
    s+=n;
    cout<<maxflow();
    return 0;
}

::::

最大权闭合子图

给一个点集，给一些选择约束关系，要让选择总和最大。假设我们已经获得所有正权点，那么我们就可以 S 往所有正权点连边，容量为权值绝对值，原图保持不变，容量为 \infty ，同理负权点连向 T，这样就把边权转移走了，如图。

::::info[图片]

::::

你发现这个东西相当于找了正权和 - 不选正权和 + 选择负权和。而目前找到的最小割是不选正权 + 要选负权值的绝对值。用正权和减去计算出的值才正确。

最大密度子图

让选择的 \frac{|E'|}{|V'|} 最大。考虑二分答案，转移不等式就是 |E'|-mid|V'|\ge 0，具体的，这就相当于一个点要付出 mid 的代价，一条边有 1 的收益，就选择边也要选两点，那么就是一个把边当做点后的最大权值闭合子图。

参考 UVA1389。

最小路径覆盖

题目：给你一个 dag，你要用若干条不交路径覆盖所有点，要求最小化路径条数。假设我们直接用 n 条单个点的路径覆盖了所有点，现在我们试图合并路径，使得路径数最小。当存在以 u 为终点，以 v 为起点的路径，这条边就能将它们合并。

问题转化，变为每个点一开始都各有一条为起点和终点的路径，边可以合并，最大化合并次数。拆点，每个点变为起点和终点，二分图最大匹配。

网络流求二分图最大匹配