首页 > 其他分享 >网络流相关技术

网络流相关技术

时间：2024-12-23 11:43:27浏览次数：4  
标签：ch return int 网络 技术 dep && 相关 fl

基础部分

最大流

Dinic

板子 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define gc getchar
ll rd(){
	ll f=1,r=0;
	char ch=gc();
	while(!isdigit(ch)){ if(ch=='-') f=-1;ch=gc();}
	while(isdigit(ch)){ r=(r<<3)+(r<<1)+(ch^48);ch=gc();}
	return f*r;
}

const int maxn=210,maxm=5010,inf=0x3f3f3f3f;
int n,m,s,t,tot=1,head[maxn],cur[maxn],dep[maxn];
ll ans;
struct edge{
	int v,nxt;
	ll f;
}e[maxm<<1];

void add(int u,int v,int w){
	e[++tot].v=v;
	e[tot].f=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}

bool bfs(){
	for(int i=1;i<=n;++i) dep[i]=0,cur[i]=head[i];
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			ll f=e[i].f;
			if(f&&!dep[v]){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t];
}

ll dfs(int u,ll fl){
	if(u==t||!fl) return fl;
	ll used=0;
	for(int i=cur[u];i&&fl;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].v;
		ll f=min(e[i].f,fl);
		if(dep[v]==dep[u]+1&&f){
			ll k=dfs(v,f);
			e[i].f-=k,e[i^1].f+=k;
			fl-=k,used+=k;
		}
	}
	if(!used) dep[u]=-1;
	return used;
}

void dinic(){
	while(bfs()) ans+=dfs(s,1e18);
}

int main(){
	n=rd(),m=rd(),s=rd(),t=rd();
	for(int i=1;i<=m;++i){
		int u=rd(),v=rd(),w=rd();
		add(u,v,w);
		add(v,u,0);
	}
	dinic();
	printf("%lld\n",ans);
	return 0;
}

时间复杂度为\(O(n^2m)\)，但大多数情况跑不满，不会被卡。但要是\(n=10^6\)了还是想想其他办法吧。

HLPP

板子 
#include<bits/stdc++.h>

using namespace std;

const int maxn=1210,maxm=120010;
int s,t,n,m,tot=1,maxh,head[maxn],h[maxn],gap[maxn];
long long ex[maxn];
stack<int> b[maxn];
struct edge{
	int v,nxt;
	long long w;
}e[maxm<<1];

void add(int u,int v,long long w){
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}

int getmxh(){
	while(b[maxh].empty()&&maxh>-1) maxh--;
	return maxh==-1?0:b[maxh].top();
}

bool bfs(){
	memset(h,0x3f3f3f3f,sizeof(h));
	h[t]=0;
	queue<int> q;
	q.push(t);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(e[i^1].w&&h[v]>h[u]+1){
				h[v]=h[u]+1;
				q.push(v);
			}
		}
	}
	return h[s]!=0x3f3f3f3f;
}

bool push(int u){
	bool p=(u==s);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v,w=p?e[i].w:min(ex[u],e[i].w);
		if(!w||(!p&&h[u]!=h[v]+1)||h[v]==0x3f3f3f3f) continue;
		if(v!=s&&v!=t&&!ex[v]) b[h[v]].push(v),maxh=max(maxh,h[v]);
		ex[u]-=w,ex[v]+=w;
		e[i].w-=w,e[i^1].w+=w;
		if(!ex[u]) return 0; 
	}
	return 1;
}

void relabel(int u){
	h[u]=0x3f3f3f3f;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(!w) continue;
		h[u]=min(h[u],h[v]+1);
	}
	if(h[u]<n){
		b[h[u]].push(u);
		gap[h[u]]++;
		maxh=max(maxh,h[u]);
	}
}

long long hlpp(){
	if(!bfs()) return 0;
	memset(gap,0,sizeof(gap));
	for(int i=1;i<=n;++i){
		if(h[i]!=0x3f3f3f3f) gap[h[i]]++;
	}
	h[s]=n,push(s);
	int u;
	while((u=getmxh())){
		b[maxh].pop();
		if(push(u)){
			if(!--gap[h[u]]){
				for(int i=1;i<=n;++i){
					if(i!=s&&i!=t&&h[i]>h[u]&&h[i]<n+1) h[i]=n+1;
				}
			}
			relabel(u);
		}
	}
	return ex[t];
}

int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;++i){
		int u,v;
		long long w;
		scanf("%d%d%lld",&u,&v,&w);
		add(u,v,w);
		add(v,u,0);
	}
	printf("%lld\n",hlpp());
	return 0;
}

时间复杂度\(O(n^2\sqrt m)\)，理论上比Dinic优秀。

一般来说不会卡Dinic，但看情况吧（

最小费用最大流

Dinic

对最大流的Dinic做一些修改就好了。

把bfs换成spfa。

这是保证流量最大时的最小费用。

板子 
#include<bits/stdc++.h>

using namespace std;

#define gc getchar
int rd(){
	int f=1,r=0;
	char ch=gc();
	while(!isdigit(ch)){ if(ch=='-') f=-1;ch=gc();}
	while(isdigit(ch)){ r=(r<<3)+(r<<1)+(ch^48);ch=gc();}
	return f*r;
}

const int maxn=5e3+10,maxm=5e4+10,inf=0x7ffffff;
int n,m,s,t,tot=1,head[maxn],cur[maxn];
int mf,mc,dis[maxn];
bool vis[maxn],inq[maxn];
struct edge{
	int v,nxt;
	int c,f;
}e[maxm<<1];

void add(int u,int v,int f,int c){
	e[++tot].v=v;
	e[tot].f=f;
	e[tot].c=c;
	e[tot].nxt=head[u];
	head[u]=tot;
}

bool spfa(){
	for(int i=1;i<=n;++i) dis[i]=inf,cur[i]=head[i],inq[i]=false;
	queue<int> q;
	q.push(s);
	dis[s]=0;
	inq[s]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=false;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,f=e[i].f,c=e[i].c;
			if(dis[v]>dis[u]+c&&f){
				dis[v]=dis[u]+c;
				if(!inq[v]) q.push(v),inq[v]=true;
			}
		}
	}
	return dis[t]!=inf;
}

int dfs(int u,int fl){
	if(u==t) return fl;
	int used=0;
	vis[u]=true;
	for(int i=cur[u];i&&fl;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].v;
		int f=min(e[i].f,fl),c=e[i].c;
		if(!vis[v]&&f&&dis[v]==dis[u]+c){
			int k=dfs(v,f);
			e[i].f-=k,e[i^1].f+=k;
			fl-=k,used+=k;
			mc+=c*k;
		}
	}
	vis[u]=false;
	return used;
}

void dinic(){
	while(spfa()){
		int x=0;
		while((x=dfs(s,inf))) mf+=x;
	}
}

int main(){
	n=rd(),m=rd(),s=rd(),t=rd();
	for(int i=1;i<=m;++i){
		int u=rd(),v=rd(),f=rd(),c=rd();
		add(u,v,f,c);
		add(v,u,0,-c);
	}
	dinic();
	printf("%d %d\n",mf,mc);
	return 0;
}

上下界网络流

无源汇上下界可行流

没有源点和汇点，每条边容量有上下界，问是否有一种给每条边标定流量的方式使得每个点流量平衡。

首先在原图上让每条边流到下界，然后给每个点计算流入的流量和流出的流量，并建立差网络（即让每条边的流量设为上界与下界之差，当做普通网络流的边）。

我们希望调整每个点的流入量或者流出量使之平衡。在差网络上建立汇源\(S\)和\(T\)，若对于点\(u\)，流入量大于流出量且差为\(x\)，就从\(S\)向\(u\)连容量为\(x\)的边，这是为了让\(u\)在差网络上继续流出，使得其平衡。同理，若流出量大于流入量且差为\(x\)，就从\(u\)向\(T\)连容量为\(x\)的边。我们称这里以\(S\)或\(T\)为端点的边为附加边。

在差网络上跑最大流后，将每条非附加边的流加上原图中的下界就是一个可行流。如果跑完最大流后发现没有满流，就说明有结点没有平衡，则不存在可行流。

判是否满流只需判断与\(S\)相连的边是否满流或者与\(T\)相连的边是否满流。根据网络流的性质，此二者要么都满流，要么都不满流。

有源汇上下界可行流

有源汇只是多了可以凭空拿出流的\(S\)和容纳所有流的\(T\)。可以简单转化成无源汇上下界可行流。只需从\(T\)向\(S\)连一条下界为\(0\)，上界为\(+\infty\)的边即可。其流量就是\(T\)到\(S\)这条边的流量。

注意：转无源汇后仍需新建源汇\(S'\)和\(T'\)来跑，原来的\(S\)和\(T\)要当做普通的点。

有源汇上下界最大流

以上，我们就已经可以求出一条可行流，现在来求最大流。

我们可以在差网络中把所有附加边删去，然后以原本的\(S\)和\(T\)作为源汇从\(S\)到\(T\)在残量网络上跑最大流，这次的最大流加上可行流即为原问题的最大流。

可行流已经保证流量平衡，这样删去附加边后不会再不平衡，然后再跑最大流相当于将原网络中还能用的流用完。

P5192 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

板子 
#include<bits/stdc++.h>

using namespace std;

#define gc getchar
int rd(){
	int f=1,r=0;
	char ch=gc();
	while(!isdigit(ch)){ if(ch=='-') f=-1;ch=gc();}
	while(isdigit(ch)){ r=(r<<3)+(r<<1)+(ch^48);ch=gc();}
	return f*r;
}

const int maxn=3e3+10,maxm=3e5+10,inf=0x7fffffff;
int n,m,s,t,s1,t1,tot=1,flow,ind[maxn],otd[maxn],head[maxn],dep[maxn],cur[maxn];
struct edge{
	int v,f,nxt;
}e[maxm<<1];

inline void add(int u,int v,int f){
	e[++tot].v=v;
	e[tot].nxt=head[u];
	e[tot].f=f;
	head[u]=tot;
}

bool bfs(){
	for(int i=1;i<=t;++i) dep[i]=0,cur[i]=head[i];
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,f=e[i].f;
			if(f&&!dep[v]){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t];
}

int dfs(int u,int fl){
	if(u==t||!fl) return fl;
	int used=0;
	for(int i=cur[u];i&&fl;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].v,f=min(e[i].f,fl);
		if(f&&dep[v]==dep[u]+1){
			int k=dfs(v,f);
			e[i].f-=k,e[i^1].f+=k;
			fl-=k,used+=k;
		}
	}
	if(!used) dep[u]=-1;
	return used;
}

int dinic(){
	int ans=0;
	while(bfs()) ans+=dfs(s,inf);
	return ans;
}

void clean(){
	tot=1;
	flow=0;
	s=s1=t=t1=0;
	memset(head,0,sizeof(head));
	memset(ind,0,sizeof(ind));
	memset(otd,0,sizeof(otd));
	return;
}

void solve(){
	clean();
	s1=n+m+1,t1=s1+1;
	add(t1,s1,inf);
	add(s1,t1,0);
	for(int i=1;i<=m;++i){
		int x=rd();
		add(i,t1,inf);
		add(t1,i,0);
		ind[t1]+=x;
		otd[i]+=x;
	}
	for(int i=1;i<=n;++i){
		int c=rd(),d=rd();
		add(s1,i+m,d);
		add(i+m,s1,0);
		for(int j=1;j<=c;++j){
			int id=rd()+1,l=rd(),r=rd();
			add(i+m,id,r-l);
			add(id,i+m,0);
			ind[id]+=l;
			otd[i+m]+=l;
		}
	}
	s=t1+1,t=s+1;
	for(int i=1;i<=t1;++i){
		if(ind[i]==otd[i]) continue;
		else if(ind[i]>otd[i]) add(s,i,ind[i]-otd[i]),add(i,s,0);
		else add(i,t,otd[i]-ind[i]),add(t,i,0);
	}
	dinic();
	for(int i=head[s];i;i=e[i].nxt){
		if(e[i].f){
			puts("-1");
			puts("");
			return;
		}
	}
	s=s1,t=t1;
	for(int i=head[t];i;i=e[i].nxt){
		if(e[i].v==s){
			flow=e[i^1].f;
			e[i].f=e[i^1].f=0;
		}
	}
	printf("%d\n\n",dinic()+flow);
	return;
}

int main(){
	while(scanf("%d%d",&n,&m)==2) solve();
	return 0;
}

有源汇上下界最小流

与上面几乎相同，只是改为从\(T\)到\(S\)跑一遍最大流，然后用可行流减去这次的流量。考虑到建图时建的反边此时当做正向的边，于是这样就相当于在不破坏平衡的前提下反悔最多的流，这样回退流量就得到最小流。

有源汇上下界最小费用可行流

注意：只是可行流，而非最大流。

和前面几乎相同。还是拆成差网络，非附加边的费用不变，附加边的费用为\(0\)。最后的最小费用即原图中流量下界与对应费用的乘积加上在差网络上用最小费用最大流跑可行流的费用。

网络流中的转化关系

最大流等于最小割

常见于将物品分到两个集合中，分到不同的集合有不同的贡献，同时有其它的特殊限制的问题。

通过建模，可以将贡献转化为在图上割去一些边的贡献，然后求最小割就拿Dinic跑一下最大流就行。

P1361 小M的作物

平面图最小割等于对偶图最短路

网络流的复杂度显然高于最短路的复杂度，这样转化自然更好。

首先介绍一下概念，平面图就是可以画在一张平面上的图，其对偶图就是将一个划分出来的区域视作点，每条边跨过原图中的一条边将各个区域连起来。注意最外面的无界区域需要特殊处理，可以视情况将其分成几个区域。

注意到在对偶图中，最短路恰好将原来的平面图分成两半，于是对应着原来的平面图的一个最小割。

P4001 [ICPC-Beijing 2006] 狼抓兔子

这里要求一个网格图中左上角到右下角的最小割，但是点数\(n\le 10^6\)，直接Dinic跑不了。

考虑转对偶图最短路，这是好转的，因为是网格图。对最外面的无界区域，我们特殊处理：沿矩形的主对角线将外面的区域分成两半，左下角作为\(s\)，右上角作为\(t\)，然后就好了。

标签：ch,return,int,网络,技术,dep,&&,相关,fl
From： https://www.cnblogs.com/EmilyDavid/p/18623612

相关文章

  • nvm npm yarn 相关配置
    一、NVM1、NVM下载安装包下载地址：https://github.com/coreybutler/nvm-windows/releases2、卸载旧版Node.js如果电脑上之前已经单独安装了Node.js，先卸载删除，环境变量也删除。3、安装解压后双击exe文件安装 安装完成后，自动添加了如下环境变量 命令行窗口输入nvm，如下......
  • 优化建图相关技术
    参考tzc_wk的博客前缀优化建图适用形式：从\(x\)向\([1,i]\)连边。从\(x\)向\([i,n]\)连边。从\([1,x]\)向\([y,n]\)连边。考虑建\(n\)个虚点\(s_i\)和\(n\)个虚点\(p_i\)。\(s_i\)代表\([1,i]\)的前缀，\(p_i\)代表\([i,n]\)的后缀。我们连边\(i\tos_i\)，\(s_i\tos_{......
  • 二分图相关技术
    基础部分二分图最大匹配P3386【模板】二分图最大匹配可网络流\(O(n\sqrtm)\)，可匈牙利\(O(nm)\)。给出匈牙利。匈牙利板子#include<bits/stdc++.h>usingnamespacestd;constintmaxn=510;intn,m,k,ans,mat[maxn];boolvis[maxn],g[maxn][maxn];booldfs(intu......
  • 拓扑序相关
    拓扑排序概念：DAG：有向无环图。拓扑排序可以对一张DAG上的顶点排序。流程：最初将入度为\(0\)的点加入队列。每次从队列中取出一个点，删去这个点的所有出边，将新产生的入度为\(0\)的点加入队列。这样按入队的先后顺序就把顶点排好序了。\(O(n+m)\)。拓扑排序在后的点只依赖......
  • 连通性相关
    基础部分DFS生成树在有向图中，DFS生成树有\(4\)种边：树边：每次搜索找到一个还未访问过的节点时就形成了一条树边。返祖边：搜索时遇到在树上的祖先节点，指向祖先的边。横叉边：搜索时遇到已访问过的节点，但该节点不是当前节点的祖先，就形成了一条横叉边。前向边：搜索时遇到了子......
  • 欧拉路相关技术
    基础部分概念：欧拉回路：经过每条边恰好一次的回路（回到起点）。欧拉通路：经过每条边恰好一次的通路（不回起点）。欧拉图：具有欧拉回路的图。半欧拉图：不具有欧拉回路，但具有欧拉通路的图。有向图强连通：任意两个顶点都可以通过有向边相互到达。有向图弱连通：将有向边换成无向边后，任意两......
  • 最短路相关技术
    板子是一定要记的，但不够，全是思维题，要解放思想开动脑筋。板子Floyd是全源最短路。只要最短路存在（无负环），不管有向无向，边权正负，都可以用。板子for(intk=1;k<=n;++k){for(inti=1;i<=n;++i){for(intj=1;j<=n;++j)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]......
  • 最小生成树相关技术
    注意只有连通图才有生成树，图不连通就只有生成森林。最小生成树的板子Kruskal基本思想是按边权从小到大加边，是贪心思想。时间复杂度\(O(m\logm)\)。板子sort(e+1,e+tot+1,cmp);for(inti=1;i<=tot;++i){ intu=e[i].u,v=e[i].v; u=find(u),v=find(v); if(u==v)continu......
  • 想转行网络安全，可以先看看过来人的建议
    在当前就业形势下，不少朋友面临转行的困境。网络安全作为一个热门领域，自然也吸引了许多人的目光。本文将就转行网络安全这一话题，提供一些切实可行的建议。网络安全行业概况网络安全涵盖了从基础的脚本编写到高级的漏洞研究等多个层面。该领域包括但不限于：渗透测试、漏洞评......
  • 深入探索人工智能的技术热点：生成式AI、强化学习与AI算法优化
    人工智能（AI）技术在不断发展中，带来了许多突破性的进展。我们看到了生成式AI在图像、文本生成等领域的广泛应用，也见证了强化学习在复杂决策问题中的成功实践。同时，随着AI技术逐渐走向实际应用，算法优化与效率提升成了新的技术焦点。在这篇博客中，我们将重点讨论目前在人工智能领域的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99