JZTXT

网络流小总结

发布时间 2023-12-13 17:54:50作者: recllect_i

\[\Huge\color{lightblue}\text{网络流启动} \]

概念

网络

边带权的有向图，只存在一个原点 \(s\) 和汇点 \(t\)。

边 \(<u,v>\) 的权值 \(c(u,v)\) 表示这个点的容量。

流

\(f(u,v)\) 满足：

  • 流量限制，即 \(f(u,v)\leq c(u,v)\)。
  • 流量守恒，即对 \(u\ne s,u\ne t\)，\(\sum f(u,v)=\sum f(v,u)\)。
  • 斜对称性，即 \(f(u,v)=-f(v,u)\)。

定义 \(f\) 的流量 \(|f|=\sum f(s,u)-\sum f(u,s)\)。

最大流

基本算法

Ford–Fulkerson 增广

定义残量 \(c(u,v)-f(u,v)\) 表示剩余的流量；对于 \(c(u,v)=0\) 的边，残量的实际意义是反向边可以退回的流量。

每次找到一条源点到汇点最小残量大于 \(0\) 的边，将路径上的边都减去最小残量，对应的，在反向边加上最小残量。把这个过程称为增广。

当不存在增广路时，则这是最大流。

特别注意，当边权为浮点数时，为了避免一些特性导致负环，松弛时需要让条件更苛刻一些。

Dinic

template <typename T, const int N, const int M, const T INF>
struct Dinic{
    int s, t;
    int la[N], cur[N], ne[M], en[M], idx = 1;
    T w[M], res = 0;
    int dis[N], q[N], hh, tt;

    inline void add_edge(int a, int b, T c)
    {
        ne[ ++ idx] = la[a];
        la[a] = idx;
        en[idx] = b;
        w[idx] = c;
    }
    inline void add(int a, int b, T c)
    {
        add_edge(a, b, c);
        add_edge(b, a, 0);
    }
    inline void add_double(int a, int b, T c)
    {
        add_edge(a, b, c);
        add_edge(b, a, c);
	}
    inline void init(int _s, int _t)
    {
        s = _s, t = _t, res = 0;
        memset(la, 0, sizeof la);
        idx = 1;
    }

    inline bool bfs()
    {
        memset(dis, -1, sizeof dis);
        q[hh = tt = 0] = s;
        dis[s] = 0;
        while(hh <= tt)
        {
            int u = q[hh ++ ];
            cur[u] = la[u];
            if(u == t) return 1;
            for(int i = la[u]; i; i = ne[i])
            {
                int v = en[i];
                if(w[i] && dis[v] == -1)
                {
                    dis[v] = dis[u] + 1;
                    q[ ++ tt] = v;
                }
            }
        }
        return 0;
    }
    inline T dfs(int u, T f)
    {
        if(u == t || !f) return f;
        T res = 0;
        for(int &i = cur[u]; i; i = ne[i])
        {
            int v = en[i];
            if(w[i] && dis[v] == dis[u] + 1)
            {
                int d = dfs(v, min(w[i], f));
                if(!d) dis[v] = -1;
                res += d, f -= d;
                w[i] -= d, w[i ^ 1] += d;
                if(!f) return res;
            }
        }
        return res;
    }
    inline T MaxFlow()
    {
        while(bfs()) res += dfs(s, INF);
        return res;
    }
};

ISAP

template <typename T, const int N, const int M, const T INF>
struct ISAP{
	int n, s, t;
	int la[N], cur[N], ne[M], en[M], idx = 1;
	T w[M];
	int dis[N], cnt[N];
	int q[N], hh, tt;
	
	inline void add_edge(int a, int b, T c)
	{
		ne[ ++ idx] = la[a];
		la[a] = idx;
		en[idx] = b;
		w[idx] = c;
	}
	inline void add(int a, int b, T c)
	{
		add_edge(a, b, c);
		add_edge(b, a, 0);
	}
	inline void init(int _n, int _s, int _t)
	{
		n = _n, s = _s, t = _t, idx = 1;
		memset(la, 0, sizeof la);
		memset(dis, 0, sizeof dis);
		memset(cnt, 0, sizeof cnt);
	}
	
	inline void bfs()
	{
		for(int i = 1; i <= n; i ++ )
		{
			dis[i] = n;
			cur[i] = la[i];
		}
		dis[t] = 0;
		q[hh = tt = 0] = t;
		while(hh <= tt)
		{
			int u = q[hh ++ ];
			cnt[dis[u]] ++ ;
			for(int i = la[u]; i; i = ne[i])
			{
				int v = en[i];
				if(w[i ^ 1] && dis[v] == n)
				{
					dis[v] = dis[u] + 1;
					q[ ++ tt] = v;
				}
			}
		}
	}
	inline T dfs(int u, T f)
	{
		if(u == t || !f) return f;
		T res = 0;
		for(int &i = cur[u]; i; i = ne[i])
		{
			int v = en[i];
			if(dis[v] == dis[u] - 1)
			{
				int d = dfs(v, min(f, w[i]));
				res += d, f -= d;
				w[i] -= d, w[i ^ 1] += d;
				if(!f || dis[s] >= n) return res;
			}
		}
		cnt[dis[u]] -- ;
		if(!cnt[dis[u]]) dis[s] = n;
		dis[u] ++ ;
		cnt[dis[u]] ++ ;
		cur[u] = la[u];
		return res;
	}
	inline T MaxFlow()
	{
		bfs();
		T res = 0;
		while(dis[s] < n) res += dfs(s, INF);
		return res;
	}
};

两种算法的比较

一般来说，如果只是一张不变的图，ISAP 的效率会略高于 Dinic。

但有的题目实测 Dinic 更快。其中一个原因是：加多路增广优化的 Dinic，在增广路短的情况下会进行很多次增广。

几道题目

危桥

首先，无向边可以当做从两端任意一个点出发，到达任意一个点，可以拆点搞了。

但还有一个问题：可能会从 \(a1\) 走到 \(b2\)。处理方法非常神奇：交换 \(b1,b2\) 重新跑网络流。

证明：设 \(a1\) 到 \(b1\) 走了 \(x\)，\(a1\) 到 \(b2\) 走了 \(y\)，不妨 \(x\leq y\)，则把 \(a1\) 到 \(b2\) 的流反向，变成 \(b2\) 到 \(a1\) 的流，合并之后就是 \(x\) 条从 \(b1\) 到 \(b2\) 的流，弥补了之前的缺憾。

最小割

对于一个流网络，将点集划分为两个集合 \(S,T\) 满足 \(s\in S,t \in T\)，称为一个割，割的容量是 \(\sum\limits_{u\in S,v\in T}c(u,v)\)。

可以证明最小割等于最大流。

划分类问题

把元素划分为 \(2\) 个集合，几种要求：

  • 如果 \(x\) 没有划分到某个集合则付出 \(w\) 的代价。
  • 如果 \(x,y\) 不在同一集合付出 \(w\) 的代价。
  • 如果集合 \(X\) 不同在某个集合，付出 \(w\) 的代价。

这些在下面题目中有体现：

方格取数
圈地计划
文理分科

染色

有些题目会有矩阵的条件，一种处理方法是染色。

圈地计划

一种处理方法是，把矩阵按坐标和奇偶性进行分组，然后就转化为不在同一集合付出代价。

老 C 的方块

最大权闭合子图

给定一张图，点有可可爱爱的点权，要求选出一个点集满足点的后继在点集中，最大化点权。

原图中的边容量为 \(\infty\)，对每个可可的点从源点向她连容量为点权的边，对每个爱爱的点从她向汇点连容量为点权绝对值的边，答案为所有可可的点权之和减最小割。

模拟最大流

有最大流，我不跑，诶就是玩。

马云买酒，可以用 HPLL 水过去。

把最大流建出的图按最小割理解，然后再转化成 DP 或者贪心之类的。

费用流

按最短路增广。

模板

单路增广

template <const int N, const int M>
struct SSP{
	int s, t;
	struct edge{
		int ne, en, c, w;
	}e[M];
	int la[N], idx = 1;
	int dis[N], pre[N];
	int vis[N], q[N], hh, tt;
	int MaxFlow = 0, MinCost = 0;
	
	inline void add_edge(int a, int b, int c, int d)
	{
		e[ ++ idx] = /*You can't get away from me, ever!*/ {la[a], b, c, d};
		la[a] = idx;
	}
	inline void add(int a, int b, int c, int d)
	{
		add_edge(a, b, c, d);
		add_edge(b, a, 0, -d);
	}
	
	inline bool spfa()
	{
		memset(dis, 0x3f, sizeof dis);
		dis[s] = 0, pre[t] = -1;
		memset(vis, 0, sizeof vis);
		hh = 0, tt = 1, q[0] = s;
		while(hh != tt)
		{
			int u = q[hh ++ ];
			if(hh == N) hh = 0;
			vis[u] = 0;
			for(int i = la[u]; i; i = e[i].ne)
			{
				int v = e[i].en;
				if(e[i].c && dis[v] > dis[u] + e[i].w)
				{
					dis[v] = dis[u] + e[i].w;
					pre[v] = i;
					if(!vis[v])
					{
						q[tt ++ ] = v;
						if(tt == N) tt = 0;
						vis[v] = 1;
					}
				}
			}
		}
		if(pre[t] == -1) return 0;
		int mx = 1e9;
		for(int u = t; u != s; u = e[pre[u] ^ 1].en)
		{
			mx = min(mx, e[pre[u]].c);
		}
		MaxFlow += mx, MinCost += dis[t] * mx;
		for(int u = t; u != s; u = e[pre[u] ^ 1].en)
		{
			e[pre[u]].c -= mx, e[pre[u] ^ 1].c += mx;
		}
		return 1;
	}
	inline void get()
	{
		while(spfa()) ;
	}
};

多路增广

template <typename T, const int N, const int M>
struct SSP{
	int s, t;
	struct Edge{
		int ne, en, c;
		T w;
	}e[M];
	int la[N], idx = 1;
	int pre[N], q[N];
	int hh, tt, vis[N];
	int MaxFlow = 0;
	T dis[N], MinCost = 0;
	
	inline void add_edge(int a, int b, int c, T d)
	{
		e[ ++ idx] = /*I Love NKOJ*/ {la[a], b, c, d};
		la[a] = idx;
	}
	inline void add(int a, int b, int c, T d)
	{
//		printf("#%d %d %d %d\n", a, b, c, d);
		add_edge(a, b, c, d);
		add_edge(b, a, 0, -d);
	}
	
	inline bool spfa()
	{
		memset(dis, 0xf3, sizeof dis);
		pre[t] = -1;
		memset(vis, 0, sizeof vis);
		dis[s] = 0, pre[s] = -1;
		q[0] = s, hh = 0, tt = 1;
		while(hh != tt)
		{
			int u = q[hh ++ ];
			if(hh == N) hh = 0;
			vis[u] = 0;
			for(int i = la[u]; i; i = e[i].ne)
			{
				int v = e[i].en;
				if(e[i].c && dis[v] < dis[u] + e[i].w)
				{
					dis[v] = dis[u] + e[i].w;
					pre[v] = i;
					if(!vis[v])
					{
						q[tt ++ ] = v;
						if(tt == N) tt = 0;
						vis[v] = 1;
					}
				}
			}
		}
		
		if(pre[t] == -1) return 0;
		memset(vis, 0, sizeof vis);
		return 1;
	}
	inline int dfs(int u, int f)
	{
		if(u == t || !f) return f;
		vis[u] = 1;
		int res = 0;
		for(int i = la[u]; i; i = e[i].ne)
		{
			int v = e[i].en;
			if(e[i].c && dis[v] == dis[u] + e[i].w && !vis[v])
			{
				int d = dfs(v, min(e[i].c, f));
				res += d, f -= d;
				e[i].c -= d, e[i ^ 1].c += d;
				MinCost += e[i].w * d;
				if(!f) return res;
			}
		}
		return res;
	}
	inline void get()
	{
		while(spfa()) MaxFlow += dfs(s, 1e9);
	}
};

zkw 费用流

不会。

题目

餐巾计划

题目。其实很多题目有用。

动态加边

美食节。

游乐场

题目。

其中包含的比较巧妙的地方：

  • 全是环等价于入度出度等于 \(1\)。
  • 分为横连和竖连，横竖间的点第一边为正，第二边为负，表示退费。

二分图最大权匹配

最长 \(k\) 可重区间集问题

题目。

上下界网络流

无源汇可行流

建立超级源汇点 \(S,T\)，对于边 \((a,b,d,u)\)，则必须流 \(b\)，所以需要从 \(b\) 到 \(a\) 流一个 \(d\) 的流，所以从 \(S\) 到 \(b\)、\(a\) 到 \(T\) 连一条容量为 \(d\) 的边，同时这条边的容量是 \(u-d\)，跑最大流。

实际运用中，可以设 \(w(u)=\sum d_{u,v}-\sum d_{v,u}\)，则当 \(w(u)>0\) 时，从 \(u\) 向 \(T\) 连容量为 \(w(u)\) 的边；当 \(w(u)<0\) 从 \(S\) 向 \(u\) 连容量为 \(-w(u)\) 的边。有可行流当且仅当最大流等于正数 \(w(u)\) 的和。

有源汇最大流

由于源点和汇点可以不流量守恒，则从汇到源容量为 \(\infty\) 的边。

有源汇最大流

第一次最大流之后，原图的流量是新加的边的流量。

把新加的边去掉，从原图的源向原图的汇增广，加上增广的流。

由于超级源和超级汇连接的边已经满流，所以不需要管。

有源汇最小流

第一次之后原图流量减源增广的流量。

template <typename T, const int N, const int M, const T INF>
struct UDF{
	Dinic<T, N + 2, M * 2 + N * 2, INF> G;
	int s, t;
	T sum[N];
	
	inline void add(int a, int b, T d, T u)
	{
//		printf("#%d %d %d %d\n", a, b, d, u);
		G.add(a, b, u - d);
		sum[a] += d, sum[b] -= d;
	}
	inline void init()
	{
		memset(sum, 0, sizeof sum);
		G.init(N, N + 1);
	}
	/*
	s = t：无源汇 
	Type = 0：有缘汇最大 
	Type = 1：有缘汇最小 
	*/
	inline int solve(int Type)
	{
		G.s = N, G.t = N + 1;
		T ss = 0;
		for(int i = 0; i < N; i ++ )
		{
			if(sum[i] < 0) G.add(G.s, i, -sum[i]);
			else if(sum[i] > 0) ss += sum[i], G.add(i, G.t, sum[i]);
		}
		G.add(t, s, INF);
		T x = G.MaxFlow();
		if(x != ss) return -1;
		if(s == t) return 0;
		T res = G.w[G.idx];
		G.s = s, G.t = t;
		if(Type) G.s = t, G.t = s;
		G.la[s] = G.ne[G.la[s]];
		G.la[t] = G.ne[G.la[t]];
		if(Type) res -= G.MaxFlow();]];
		else res += G.MaxFlow();
		return res;
	}
};
UDF<int, 1005, 300005, 100> G;

无源汇最小费用流

类似前面建图，费用来自两个方面：

  • 流满下界的费用，即 \(bw\)。
  • 增广的费用。
    如果不存在负环，第一次增广之后原图的源到原图的汇没有负权增广路，可以直接返回。

如果需要保证最大流，按照之前的方法增广。

template <const int N, const int M>
struct CUDF{
	SSP<N + 2, M * 2 + N * 2> G;
	int sum[N], res = 0;
	
	inline void add(int a, int b, int d, int u, int c)
	{
//		printf("#%d %d %d %d %d\n", a, b, d, u, c);
		G.add(a, b, u - d, c);
		sum[a] += d, sum[b] -= d, res += c * d;
	}
	inline int solve()
	{
		G.s = N, G.t = N + 1;
		int s = 0;
		for(int i = 0; i < N; i ++ )
		{
			if(sum[i] < 0) G.add(G.s, i, -sum[i], 0);
			else if(sum[i] > 0) s += sum[i], G.add(i, G.t, sum[i], 0);
		}
		G.get();
		return G.MaxFlow == s ? res + G.MinCost : -1;
	}
};

带负圈费用流

类似于上下界网络流，当费用为正不管，费用为负，假设它满流，然后超级源向 \(b\) 连 \((c,0)\) 的边，\(a\) 向超级汇连 \((c,0)\) 的边，然后加上满流的费用，加反向负费用边。

优化与其它部分与上下界网络流类似。

template <const int N, const int M>
struct NCF{
	SSP<N + 2, M * 2 + N * 2> G;
	int s, t, sum[N], res = 0, mf;
	inline void add(int a, int b, int c, int d)
	{
		if(d >= 0)
		{
			G.add(a, b, c, d);
		}
		else
		{
			res += c * d;
			G.add(b, a, c, -d);
			sum[a] -= c, sum[b] += c;
		}
	}
	inline void solve()
	{
		G.s = N, G.t = N + 1;
		for(int i = 0; i < N; i ++ )
		{
			if(sum[i] > 0) G.add(G.s, i, sum[i], 0);
			if(sum[i] < 0) G.add(i, G.t, -sum[i], 0);
		}
		G.add(t, s, 1e9, 0);
		G.get();
		res += G.MinCost, mf = G.e[G.idx].c;
        G.s = s, G.t = t;
        G.la[s] = G.e[G.la[s]].ne;
        G.la[t] = G.e[G.la[t]].ne;
        G.MaxFlow = G.MinCost = 0;
        G.get();
        res += G.MinCost, mf += G.MaxFlow;
	}
};

\[\Huge\color{lightblue}\text{结束吗？不会的！} \]