网络流

yangzichen1203 · 2026-04-22 22:06:36 · 算法·理论

Dinic 模版

#define inf (1ll<<60)
class Dinic{
    private:
        struct Edge{
            int to,rev;
            long long cap;
        };
        int n;
        vector<vector<Edge>> g;
        vector<int> dis,it;
        bool bfs(int s,int t){
            fill(dis.begin(),dis.end(),0);
            queue<int> q;
            dis[s]=1;
            q.push(s);
            while(!q.empty()){
                int u=q.front();
                q.pop();
                for(auto &e:g[u]){
                    if(!dis[e.to]&&e.cap>0){
                        dis[e.to]=dis[u]+1;
                        q.push(e.to);
                    }
                }
            }
            return dis[t]!=0;
        }
        long long dfs(int u,int t,long long f){
            if(u==t) return f;
            for(int &i=it[u];i<(int)g[u].size();i++){
                Edge &e=g[u][i];
                if(e.cap<=0) continue;
                if(dis[e.to]!=dis[u]+1) continue;
                long long push=dfs(e.to,t,min(f,e.cap));
                if(push>0){
                    e.cap-=push;
                    g[e.to][e.rev].cap+=push;
                    return push;
                }
            }
            return 0;
        }
    public:
        Dinic(int n=0):n(n){
            g.assign(n+1,{});
            dis.assign(n+1,{});
            it.assign(n+1,{});
        }
        void add(int u,int v,long long w){
            int szu=g[u].size(),szv=g[v].size();
            g[u].push_back({v,szv,w});
            g[v].push_back({u,szu,0});
        }
        long long maxflow(int s,int t){
            long long flow=0;
            while(bfs(s,t)){
                fill(it.begin(),it.end(),0);
                while(1){
                    long long push=dfs(s,t,inf);
                    if(!push) break;
                    flow+=push;
                }
            }
            return flow;
        }
};

1

https://www.luogu.com.cn/problem/P1361

https://www.luogu.com.cn/problem/P1646

https://www.luogu.com.cn/problem/P4313 :::success[Solution] 很明显的二分图，考虑最小割。

对于点 i，考虑把 A 侧贡献放在边 (S,i,a_i) 上，把 B 侧贡献放在边 (i,T,b_i) 上。

如果割掉 (S,i,a_i)，代表选 B 侧，那么就不能得到选 A 侧的贡献，我们就想办法使得此时一定要割掉同时选 A 的额外收益，于是建 (S,x,c_{1,x}),(x,i,+\infty)，另一侧类似地建 (x,T,c_{2,x}),(i,x,+\infty)。

对于选 0 的人，连 (S,i,1)；对于选 1 的人，连 (i,T,1)。

对于点对 (i,j)，连 (i,j,1),(j,i,1)。

很显然这样建图后之间跑最小割即可。

https://www.luogu.com.cn/problem/P4474

:::success[Solution] 我们需要割掉一些点的贡献来保证方案合法，考虑最小割。

对于这种网格图相邻不能取的问题，可以将网格图的点 (x,y) 按 (x+y)\bmod 2 分成 2 类，就转换为一张二分图。

对于 (i+j)\bmod 2=0 类，建 (S,(i,j),a_{i,j})；对于 (i+j)\bmod 2=1 类，建 ((i,j),T,a_{i,j})。

对于不能取相邻点对，只需要建源点侧向汇点侧建边，所以当 (i+j)\bmod 2=0 时建 ((i,j),(i\pm1,j\pm1),+\infty)。 :::

4

https://www.luogu.com.cn/problem/P1402

https://www.luogu.com.cn/problem/P1231 :::success[Solution] 最大流。

每个人左侧连房间，容量为 1，右侧连菜，容量为 1，为了保证每个人最多贡献一次，把每个人拆成两个点，中间连容量为 1 的边。

源点向狼连容量为 +\infty 的边，羊向汇点连容量为 +\infty 的边，每个点向四周点连容量为 1 的边。

https://www.luogu.com.cn/problem/P4174

https://www.luogu.com.cn/problem/P3749 :::success[Solution] 最大权闭合子图。

让收入减小量加上支出增加量最小，考虑最小割。

思想是如果我们割掉所有收入，我们就可以不割掉支出。

那么对于一个收入 v_{i,j}，连 (S,x,v_{i,j}),(x,i,+\infty),(x,j,+\infty)；对于一个支出 w_i，连 (i,T,w_i)。

答案就是 \sum v-maxflow。

平面图的最小割等于其对偶图的最短路，不需要跑网络流。

发现一定是一个 0 在中间，1 和 2 在这个 0 两端相邻时非法。所以建图时 0 左侧连 1，右侧连 2，对 0 拆点。

跑一遍最小割即可。

考虑如何表示限制。每个人维护一条链 S\to1\to2\to\dots\to m\to T，链上每条边放它后面表示的套题的期望奖励，求最小割。

那么一个限制就可以表示为一些连接两条链的斜向边，如 i 比 j 至少大 k 可以被表示为 ((j,x),(i,\min(x+k,m)),+\infty) 的形式。