首页 > 编程语言 >[算法] A LITTLE 网络流

[算法] A LITTLE 网络流

时间:2024-09-26 10:50:48浏览次数:8  
标签:LITTLE 增广 int 网络 long 算法 cnt dis

简介

所谓网络流,就是给了一张图,有源点和汇点,让你求从源点放水,到汇点的水最多能有多少;

这实际上是一个最大流的问题;

最大流

我们把这张图的每个边看作一条水管,每个水管都有一个容量,那么对于一条从源点到汇点的路径,其最大通过量是这些水管中容量最小的那一个的容量;

对于这个问题,我们有如下的处理方法:

EK 算法

定义一条增广路为从源点(设为s)到汇点(设为t)的一条路径,满足其所有边的剩余容量非负;

对于此算法,我们每次都找一条增广路,然后更新每条边的权值直到剩余图中(也即残量网络)没有增广路;

因为我们要重新找增广路,所以还要建反向边,便于回去重新找;

可以看出,它的复杂度瓶颈在边数

那么最坏情况是每次只能确定一条边,时间复杂度 $ O(nm^2) $,不太适用于稠密图,但实际使用其实达不到此上界;

因为下一个算法使用较普遍,所以这里就不放代码;

Dinic 算法

考虑对于一个残量网络,EK算法会重新遍历整个残量网络,然后只找出一条增广路,考虑将复杂度瓶颈由边转移到点;

于是有了Dinic算法;

首先对图进行分层(就是进行一边BFS,然后将遍历顺序(即深度)相同的点纳入同一层);

然后每次处理一层的所有点的增广路,直到残量网络不能分层(即s不能到达t);

我们发现,它和EK的本质区别在于它是以点为单位(每次分层是 $ \Theta(n) $ 的)找增广路,而前者是以边为单位;

时间复杂度: $ O(n^2m) $;

当然,它还有两个优化:当前弧优化和剪枝;

前者是在当前层中只去找能扩展的边,后者是去掉增广完毕的点;

点击查看代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, m, s, t;
struct sss{
	int t, ne;
	long long w;
}e[200005];
int h[200005], cnt;
void add(int u, int v, long long ww) {
	e[++cnt].t = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
	e[cnt].w = ww;
}
int now[200005];
long long ans;
int dis[205];
bool bfs() { //点分层;
	queue<int> q;
	for (int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
	q.push(s);
	now[s] = h[s];
	dis[s] = 0;
	while(!q.empty()) {
		int tt = q.front();
		q.pop();
		for (int i = h[tt]; i; i = e[i].ne) {
			int u = e[i].t;
			if (e[i].w > 0 && dis[u] == 0x3f3f3f3f) {
				dis[u] = dis[tt] + 1;
				now[u] = h[u];
				q.push(u);
				if (u == t) return true;
			}
		}
	}
	return false;
}
long long dfs(int x, long long sum) {
	if (x == t) return sum;
	long long k = 0; //当前最小剩余流量;
	long long res = 0; //流过点x的总流量;
	for (int i = now[x]; i; i = e[i].ne) {
		int u = e[i].t; 
		now[x] = i; //当前弧优化;
		if (e[i].w > 0 && (dis[u] == dis[x] + 1)) {
			k = dfs(u, min(sum, e[i].w));
			if (k == 0) dis[u] = 0x3f3f3f3f; //剪枝;
			e[i].w -= k;
			e[i ^ 1].w += k;
			res += k;
			sum -= k; //sum是经过该点的剩余流量;
		}
	}
	return res;
}
void Dinic() {
	while(bfs()) {
		ans += dfs(s, 0x3f3f3f3f3f3f3f3f);
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> s >> t;
	int u, v;
	long long w;
	cnt = 1;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, 0);
	}
	Dinic();
	cout << ans;
	return 0;
}

To be continued...

标签:LITTLE,增广,int,网络,long,算法,cnt,dis
From: https://www.cnblogs.com/PeppaEvenPig/p/18433017

相关文章

  • 算法与数据结构——简单排序算法(选择、冒泡、插入)
    简单排序算法时间复杂度均为O(n2)选择排序选择排序(selectionsort)的工作原理非常简单:开启一个循环,每轮从未排序区间选择最小的元素,将其放到已排序的区间的末尾。算法流程设数组长度为n,选择排序的算法流程如下。初识状态下,所有元素未排序,即未排序(索引)区间为[1,n-1]。选取......
  • 操作系统-页面置换算法
    简介期末考试中常考的页面置换算法可能有三种,分别是先进先出(FIFO),最佳置换(OPT)和最久未使用(LRU)本篇文章会用一道例题来讲解这三种算法的思路和解题过程;题目假设有这样一个操作系统,其内存中有3个空闲页面框(题目也有可能是描述成M3,M是Memory的简写)。进程依次请求页面号为以下序......
  • 计算机网络中的VLAN详解
    文章目录计算机网络中的VLAN详解一、引言二、VLAN的作用与原理1、VLAN的作用2、VLAN的工作原理2.1、VLAN标签(Tag)三、VLAN的配置与接口类型1、VLAN的配置2、接口类型四、VLAN的应用场景1、企业网络2、数据中心3、教育网络五、VLAN间的通信六、总结计算机网络中的V......
  • 强联通分量——Tarjan算法
    Tarjan算法详解参考文章:强连通分量Tarjan算法是一种用于寻找有向图中强联通分量(StronglyConnectedComponents,SCCs)的算法。它是由RobertTarjan在1972年提出的,基于深度优先搜索(DFS)和栈的数据结构。基本概念强联通分量:在一个有向图中,如果一组节点中任意两个节点都可以互相......
  • Tarjan算法缩点
    Tarjan算法缩点一.Tarjan算法缩点详解在图论中,缩点是指将有向图中的强联通分量(SCCs)缩成单个节点,从而得到一个更简单的图结构,称为缩点图或SCC图。Tarjan算法不仅可以用来寻找强联通分量,还可以用来进行缩点操作。基本概念强联通分量:在一个有向图中,如果一组节点中任意两个节点都......
  • ShiftAddAug:基于乘法算子训练的最新无乘法网络方案 | CVPR'24
    不包含乘法的运算符,如移位和加法,因其与硬件的兼容性而日益受到重视。然而,采用这些运算符的神经网络(NNs)通常表现出比具有相同结构的传统NNs更低的准确性。ShiftAddAug利用成本较高的乘法来增强高效但功能较弱的无乘法运算符,从而在没有任何推理开销的情况下提高性能。将一个ShiftAd......
  • CentOS8使用chrony同步网络时间
    文章目录引言ICentOS8使用chrony网络时间同步安装chrony配置间同步服务器地址检查本机的时区设置时区chronyc命令IIwindows网络时间同步2.1修改同步服务器2.2修改同步频率引言应用场景:获取服务器时间进行船舶在线率统计dtos.forEa......
  • nload实时监网络流量信息
    nload用于实时监控linux下网络流量信息,是命令行工具,用来监控网络的吞吐量。它使用两个图表数据来对进出站流量进行可视化。一、安装nload[root@localhost~]#yuminstallepel-release.noarch-y[root@localhost~]#yuminstallnload.x86_64-y二、命令nload详解1、命令......
  • 算法-复杂度分析
    复杂度分析不依赖具体的执行环境不用具体的测试数据在算法实现前,我们在脑海就可以评估算法的性能评估一个算法的性能:本质上就是评估这个算法代码执行的时间N为数据规模 大O复杂度表示法表示算法的性能,通常看最差的情况,算法运行的上界O(n) T=5n+2常数不重要,复杂......
  • 【算法】C++KMP算法的简洁实现
    目录简介next数组匹配完整代码简介对于朴素的字符串匹配算法,如果想在主串中寻找到第一次出现子串的位置,需要依次枚举主串中的每一个位置作为起始位置进行匹配尝试,如果主串中存在许多与子串相似结构的部分,那么朴素算法会进行大量的无用枚举,时间复杂度非常之高。KMP算法......