首页 > 其他分享 >网络流小总结

网络流小总结

时间：2023-12-13 17:55:34浏览次数：33  
标签：总结 la int sum 网络 流小 add inline dis

\[\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{结束吗？不会的！} \]

标签：总结,la,int,sum,网络,流小,add,inline,dis
From： https://www.cnblogs.com/recollect-the-past/p/17899617.html

相关文章

  • 遇到攻击怎么办，有什么办法解决网络层和应用层的DDoS攻击
    随着网络普及，互联网安全形势面临频繁的攻击和威胁，主要威胁之一就是DDoS攻击。DDOS是一种常见的网络攻击，可以通过网络层和应用层进行攻击。我们就来简单了解下网络层DDoS攻击和应用层DDoS攻击，以及面对流量攻击有什么解决方案。网络层DDoS攻击和应用层DDoS攻击是两种不同类型的分布式......
  • 我是怎么解决 tiktok 直播时的网络问题
    随着社交媒体平台TikTok的兴起，直播功能成为用户分享和互动的重要方式。TikTok直播吸引了大量用户参与，让用户能够分享才艺、生活和观点。然而，随着用户数量的增加，网络连接和稳定性面临着挑战，影响了直播的质量和观众的体验。为了解决这些问题，本文将分享TikTok直播网络环境搭建的......
  • k8s网络
    Kubernetes本身并不负责网络通信，Kubernetes提供了容器网络接口CNI（ContainerNetworkInterface），具体的网络通信交给CNI插件来负责，开源的CNI插件非常多，像Flannel、Calico。Kubernetes虽然不负责网络，但要求集群中的Pod能够互相通信，且Pod必须通过非NAT网络连接，即收到的数据包的源IP......
  • 园区网络虚拟化应该这样建
    下午好，我的网工朋友。今天和你聊聊怎么建立园区网络虚拟化。区别于传统园区关注独立的单台设备，虚拟化网络关注全网的整体业务体验，通过iMasterNCE-Campus和VXLAN技术，实现网络资源能够任意灵活调度。通过虚拟化技术，将物理网络资源进行池化处理，形成可供业务层任意调动的全网资源池，供i......
  • 2023十大优质国产原厂品牌网络评选活动！
    助力国产替代，振兴中国芯片！“道合顺2023十大优质国产原厂品牌网络评选”正式开启~投票有机会抽中国黄金金条、华为Mate60手机，小米扫地机器人等壕礼~！戳>https://www.icdhs.com/activity/brandvote2023/?source=51......
  • 使用网络蜘蛛的流程●网络爬虫织网步骤
    蜘蛛池是一种通过大量模拟真实用户行为来提升网站搜索引擎排名的技术。这种技术利用大量的网络爬虫程序，模拟搜索引擎蜘蛛的爬行行为，通过大量的模拟爬行和页面抓取，提高网站的权重和排名。现代社会，网络蜘蛛广泛应用于搜索引擎、数据挖掘、舆情分析、商业竞争等领域。那么，使用网络爬......
  • @Async总结
    使用场景：开发中会碰到一些耗时较长或者不需要立即得到执行结果的逻辑，比如消息推送、商品同步等都可以使用异步方法，这时我们可以用到@Async。但是直接使用@Async会有风险，当我们没有指定线程池时，他会默认使用其Spring自带的SimpleAsyncTaskExecutor线程池，会不断的创建线程，当并发......
  • 网络多级路由电脑配置
    网络多级路由电脑配置 公司内网----->路由器----->公司电脑 ----->服务器 ----->打印机 ----->路由器----->我的电脑二级路由访问一级路由（我的电脑访问服务器）: PC1    TP-LINK PC2二级路由(192.168.......
  • mysql花式操作数据小技巧总结
    mysql花式操作数据小结本文是一片关于一些mysql小技巧的总结。主要内容包括：字段中包含多值、基于字段中某个值查询、基于身份证设置性别、身份证生成出生日期、增加表字段、一次搞定多个查询、关联删除、通过关系表一对多查询合并到一条记录、替代like1.字段中包含多值字段为cro......
  • Vue3 setup 方法的一些基本使用总结
    官网介绍：https://cn.vuejs.org/api/composition-api-setup.html基本使用setup()钩子是在组件中使用组合式API的入口，通常只在以下情况下使用：需要在非单文件组件中使用组合式API时。需要在基于选项式API的组件中集成基于组合式API的代码时。setup方法返回值：返回一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99