首页 > 其他分享 ><学习笔记> 网络流

<学习笔记> 网络流

时间：2023-12-05 09:23:18浏览次数：29  
标签：head dist int 网络 st dep edge

最大流

code 
queue<int> q;
int dep[N],cur[N];
int bfs(){
	memset(dep,0,sizeof(dep));
	q.push(st);
	dep[st]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nex[i]){
			int y=ver[i];
			if(dep[y] || !edge[i]) continue;
			dep[y]=dep[x]+1;
			q.push(y);
		}
	}
	if(dep[ed]) return 1;
	else return 0;
}
int dfs(int x,int flow){
	if(x==ed) return flow;
	for(int i=cur[x];i;i=nex[i]){
		cur[x]=i;
		int y=ver[i];
		if(dep[y]==dep[x]+1 && edge[i]){
			int d=dfs(y,min(flow,edge[i]));
			if(d>0){
				edge[i]-=d;
				edge[i^1]+=d;
				return d;
			}
		}
	}
	return 0;
}
int Dinic(){
	int ans=0;
	while(bfs()){
		for(int i=1;i<=ed;i++){
			cur[i]=head[i];
		}
		while(int d=dfs(st,inf)){
			ans+=d;
		}
	}
	return ans;
}

最大流最小割定理

对于一个网络流图 \(G=(V,E)\) 的最小割等于其最大流。

问题模型：

有 \(n\) 个物品和两个集合 \(A,B\) ，如果一个物品没有放入 \(A\) 集合会花费 \(a_i\) ，没有放入 \(B\) 集合会花费 \(b_i\) ；还有若干个形如 \(u_i,v_i,w_i\) 限制条件，表示如果 \(u_i\) 和 \(v_i\) 同时不在一个集合会花费 \(w_i\) 。每个物品必须且只能属于一个集合，求最小的代价。

线性代数

先钦定 \(b\) 的贡献全算上，然后考虑减少的量，要使其最小，又发现 \(a_i\) 等于 \(0,1\) 有不同贡献，\(a_i\) 和 \(a_j\) 组合又有不同贡献，所以考虑最小割，会有一下关系：

\[a+b=c_x+c_y (x,y=1) \]

\[c+d=b_{xy}+b_{xx}+b_{yy}+b_{yx} (x,y=0) \]

\[a+d+v2=c_x+b_{xy}+b_{yy}+b_{yx} (x=1,y=0) \]

\[b+c+v1=c_y+b_{xy}+b_{yx}+b_{xx} (x=0,y=1) \]

用解方程的方法让 \(a=c_x , b=c_y , c=b_{xx}+b_{xy} , d=b_{yy}+b_{yx}\)，然后求出 \(v_1,v_2\)，给 \(c,d\)求个和发现 \(c=\sum_{i}b_{xi}\) \(d=\sum_{i}b_{yi}\)。

费用流

每回 \(spfa\) 找费用最小的流。

code 
queue<int> q;
int gpre[N],gpath[N];
int dist[N];
int spfa(int s,int t){
	memset(gpre,-1,sizeof(gpre));
	memset(dist,0x7f,sizeof(dist));
	q.push(s);
	dist[s]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nex[i]){
			int y=ver[i];
			if(edge[i] && dist[y]>dist[x]+cost[i]){
				dist[y]=dist[x]+cost[i];
				gpre[y]=x;
				gpath[y]=i;
				q.push(y);
			}
		}
	}
	if(gpre[t]==-1) return 0;
	else return 1;
}
pair<int,int> EKF(){
	int flow=0;
	int ct=0;
	while(spfa(s,t)){
		int mi=(1ll<<20);
		for(int x=t;x!=s;x=gpre[x]){
			mi=min(mi,edge[gpath[x]]);
		}
		flow+=mi;
		for(int x=t;x!=s;x=gpre[x]){
			ct+=cost[gpath[x]]*mi;
			edge[gpath[x]]-=mi;
			edge[gpath[x]^1]+=mi;
		}
	}
	return make_pair(flow,ct);
}

上面是保证最大流的前提下最小费用，下面是保证最小费用前提下最大流（相当于可行流）（区别很小）

code 
int gpre[N*2],gpath[N*2],dist[N*2];
bool flat[N*2];
queue<int> q; 
int spfa(int s,int t){
	memset(gpre,-1,sizeof(gpre));
	memset(dist,0x7f,sizeof(dist));
	q.push(s);
	dist[s]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nex[i]){
			int y=ver[i];
			if(edge[i] && dist[y]>dist[x]+cost[i]){
				dist[y]=dist[x]+cost[i];
				gpre[y]=x;
				gpath[y]=i;
				q.push(y);
			}
		}
	}
	if(gpre[t]==-1) return 0;
	else return 1;
}
int n,m,k;
int cnt=(1ll<<60);
int EKF(){
	int ct=0;
	while(m--&&spfa(st,ed)){//---------------------------------------------<---------
		int mi=1e9;
		for(int x=ed;x!=st;x=gpre[x]){
			mi=min(mi,edge[gpath[x]]);
		}
		int qwe=0;
		for(int x=ed;x!=st;x=gpre[x]){
			qwe+=cost[gpath[x]]*mi;
			edge[gpath[x]]-=mi;
			edge[gpath[x]^1]+=mi;
		}
		if(qwe>0) continue; 
		ct+=qwe;
	}
	return ct;
}

有上下界的网络流

  • 无源汇有上下界可行流(也就是循环流)

可行流算法的核心是将一个不满足流量守恒的初始流调整成满足流量守恒的流。

我们一开始钦定每条边的流量为其下界，可以注意到的是此时每个点的入流量不等于出流量，将这个流量定义初始流。

所以我们进行调整，将原图的容量全部改为 \(up-down\)，这样如何调整总流量都在范围内，定义数组 \(A_i\) 等于 \(i\) 的入流量减去出流量。为了满足流量守恒，我们考虑在残量网络上求出一个另不满足流量守恒的附加流，使得这个附加流和我们的初始流合并之后满足流量守恒。

定义源点 \(st\)，汇点 \(ed\)。如果一个点 \(A_i>0\) 相当于要求附加流出流量大于入流量，为了让多出的出流量有一个来路，所以 \(st \rightarrow i\)，容量为 \(|A_i|\)；如果一个点 \(A_i<0\) 相当于要求附加流入流量大于出流量，为了让多出的入流量有一个出路，所以 \(i \rightarrow ed\)，容量为 \(|A_i|\)。

可以发现 \(A_i\) 之和为 \(0\)，因为每条边对两边的贡献互为相反数，设正 \(sum=\sum A_i (A_i>0)\)。

我们对 \(st-ed\) 跑最大流，如果最大流等于 \(sum\)，也就是可以跑满，说明有可行流的，反之没有。最后每条边可行流的流量 \(=\) 容量下界 \(+\) 附加流流量（跑完后反向边权值）

  • 有源汇有上下界可行流

建出图 \(sst-eed\) 之后连一条 \(eed \rightarrow sst\) 下界为 \(0\)，上界为正无穷的边，转化为无源汇有上下界可行流，最后跑出来的可行流大小其实为 \(eed \rightarrow sst\) 反向边的大小。

  • 有源汇有上下界最大流

我们跑完的可行流不一定是最大的，所以我们再在 \(sst-eed\) 之间的残余网络中跑最大流，最后 答案 \(=\) 可行流 \(+\) 之后跑的最大流。

注意这里判断是否可行是看 \(st-ed\) 最大流是否等于 \(sum\)。可行流的大小等于 \(eed \righttarrow sst\) 反向边的大小，别混淆。

例题Zoj3229 Shoot the Bullet

code 
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int inf=0x7f7f7f7f;
int st,ed;
int head[maxn],ver[maxn*maxn],nex[maxn*maxn],edge[maxn*maxn],tot=1;
void add(int x,int y,int v){
    ver[++tot]=y,nex[tot]=head[x],head[x]=tot,edge[tot]=v;
    ver[++tot]=x,nex[tot]=head[y],head[y]=tot,edge[tot]=0;
}
int A[maxn];
queue<int> q;
int dep[maxn],cur[maxn];
int bfs(){
    memset(dep,0,sizeof(int)*(ed+1));
    dep[st]=1;
    q.push(st);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nex[i]){
            int y=ver[i];
            if(edge[i]<=0 || dep[y]) continue;
            dep[y]=dep[x]+1;
            q.push(y);
        }
    }
    if(dep[ed]) return 1;
    else return 0;
}
int dfs(int x,int flow){
    if(x==ed) return flow;
    for(int i=cur[x];i;i=nex[i]){
        cur[x]=i;
        int y=ver[i];
        if(dep[y]==dep[x]+1 && edge[i]>0){
            int d=dfs(y,min(flow,edge[i]));
            if(d>0){
                edge[i]-=d;
                edge[i^1]+=d;
                return d;
            }
        }
    }
    return 0;
}

int Dinic(){
    int ans=0;
    while(bfs()){
        for(int i=1;i<=ed;i++){
            cur[i]=head[i];
        }
        while(int d=dfs(st,inf)){
            ans+=d;
        }
    }
    return ans;
}
signed main(){
    // freopen("P5192_1.in","r",stdin);
    // freopen("in.in","r",stdin);
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        memset(A,0,sizeof(A));
        tot=1;
        memset(head,0,sizeof(head));
        int sst=n+m+1,eed=sst+1;
        st=eed+1,ed=st+1;
        for(int i=1;i<=m;i++){
            int g;
            scanf("%d",&g);
            add(n+i,eed,inf-g);
            A[eed]+=g;
            A[n+i]-=g;
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            int c,d;
            scanf("%d%d",&c,&d);
            add(sst,i,d);
            for(int j=1;j<=c;j++){
                int t,l,r;
                scanf("%d%d%d",&t,&l,&r);
                t++;
                add(i,n+t,r-l);
                A[i]-=l;
                A[n+t]+=l;
            }
        }
        add(eed,sst,inf);
        int pos=tot;
        for(int i=1;i<=eed;i++){
            if(A[i]==0) continue;
            if(A[i]<0) add(i,ed,-A[i]);
            else add(st,i,A[i]);
            if(A[i]>0) sum+=A[i];
        }
        if(Dinic()!=sum){
            printf("-1\n\n");
        }
        else{
            int ans=edge[pos];
            for(int i=head[st];i;i=nex[i]){
                edge[i]=edge[i^1]=0;
            }
            for(int i=head[ed];i;i=nex[i]){
                edge[i]=edge[i^1]=0;
            }
            for(int i=head[sst];i;i=nex[i]){
                if(ver[i]==eed){
                    edge[i]=edge[i^1]=0;
                }
            }
            st=sst,ed=eed;
            ans+=Dinic();
            printf("%d\n\n",ans);
        }
    }
}

  • 有源汇上下界最小流

考虑反边的含义，反边每增加一，相当于正边减小一，所以我们给 \(sst-eed\) 反边跑最大流，那么 答案 \(=\) 可行流 \(-\) 反边最大流。

例题清理雪道

code 
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000;
const int inf=(1<<20);
int st,ed;
int head[maxn*2],nex[maxn*maxn],ver[maxn*maxn],edge[maxn*maxn],tot=1;
void add(int x,int y,int v){
    ver[++tot]=y,nex[tot]=head[x],head[x]=tot,edge[tot]=v;
    ver[++tot]=x,nex[tot]=head[y],head[y]=tot,edge[tot]=0;
}
int A[maxn*maxn];
queue<int> q;
int dep[maxn],cur[maxn];
int bfs(){
    memset(dep,0,sizeof(int)*(max(st,ed)+1));
    dep[st]=1;
    q.push(st);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nex[i]){
            int y=ver[i];
            if(edge[i]<=0 || dep[y]) continue;
            dep[y]=dep[x]+1;
            q.push(y);
        }
    }
    if(dep[ed]) return 1;
    else return 0;
}
int dfs(int x,int flow){
    if(x==ed) return flow;
    for(int i=cur[x];i;i=nex[i]){
        cur[x]=i;
        int y=ver[i];
        if(dep[y]==dep[x]+1 && edge[i]>0){
            int d=dfs(y,min(flow,edge[i]));
            if(d>0){
                edge[i]-=d;
                edge[i^1]+=d;
                return d;
            }
        }
    }
    return 0;
}
int Dinic(){
    int ans=0;
    while(bfs()){
        int mx=max(ed,st);
        for(int i=1;i<=mx;++i){
            cur[i]=head[i];
        }
        while(int d=dfs(st,inf)){
            ans+=d;
        }
    }
    return ans;
}
signed main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int m;
        scanf("%d",&m);
        for(int j=1;j<=m;j++){
            int x;
            scanf("%d",&x);
            add(i,x,inf-1);
            A[i]--,A[x]++;
        }
    }
    int sst=n*2+1,eed=sst+1;
    st=eed+1,ed=st+1;
    for(int i=1;i<=n;i++){
        add(sst,i,inf);
        add(i,eed,inf);
    }
    add(eed,sst,inf);
    int pos=tot;
    int sum=0;
    for(int i=1;i<=eed;i++){
        if(A[i]==0) continue;
        if(A[i]<0) add(i,ed,-A[i]);
        else add(st,i,A[i]);
        if(A[i]>0) sum+=A[i];
    }
    Dinic();
    int ans=edge[pos];
    for(int i=head[st];i;i=nex[i]){
        edge[i]=edge[i^1]=0;
    }
    for(int i=head[ed];i;i=nex[i]){
        edge[i]=edge[i^1]=0;
    }
    for(int i=head[sst];i;i=nex[i]){
        if(ver[i]==eed){
            edge[i]=edge[i^1]=0;
        }
    }
    st=eed,ed=sst;
    ans-=Dinic();
    printf("%d",ans);
}

参考资料

标签：head,dist,int,网络,st,dep,edge
From： https://www.cnblogs.com/jinjiaqioi/p/17875136.html

相关文章

  • 2023-2024-1学期 20232316戴露 《网络空间安全导论》第五章学习总结
    信息内容洪流中何去何从（第五章内容安全基础）依我看来，本章节围绕网络空间安全中一个重要关键词“信息内容安全”展开了详细论述。个人梳理了此章节的整体逻辑框架，大致可分为是什么，为什么和怎么做三个方面来展开是什么信息内容安全的背景互联网朝着开放性、异构性、移动性、动......
  • 夜莺专业版网络设备功能介绍
    网络设备采集简介网络设备的问题通常会产生较大范围的影响，因此采集监控网络设备是一项常见的任务。不同公司在实施网络设备采集时可能采用不同的方案，主要有三类：SNMP（SimpleNetworkManagementProtocol）：SNMP是一种常用的网络管理协议，可以用于获取网络设备的状态和性能信息。大......
  • 简化的社交网络系统
    以下是一个使用Python编写的复杂数据结构示例，这是一个简化的社交网络系统：classPerson:def__init__(self,name,age):self.name=nameself.age=ageself.friends=[]defadd_friend(self,friend):self.friends.append(friend......
  • 智安网络|语音识别技术：从历史到现状与未来展望
    语音识别技术是一种将语音信号转化为可识别的文本或命令的技术，近年来得到了广泛应用和关注。一.语音识别的发展现状1.历史发展语音识别技术的起源可以追溯到20世纪50年代，但直到近年来取得了显著的突破和进展。随着计算机性能的提升和深度学习算法的发展，语音识别技术在准确性和速......
  • ADAudit Plus：强大的网络安全卫士
    随着数字化时代的不断发展，企业面临着越来越复杂和多样化的网络安全威胁。在这个信息爆炸的时代，保护组织的敏感信息和确保网络安全已经成为企业发展不可或缺的一环。为了更好地管理和监控网络安全，ADAuditPlus应运而生，成为网络安全领域的卫士之一。ADAuditPlusADAuditPlus是一款功......
  • 代理IP、Socks5代理与爬虫在跨界电商与游戏领域的网络安全应用
    的数据挖掘，企业可以及时调整战略，把握市场机会，实现更好的出海业务。2.游戏领域的爬虫应用在游戏领域，爬虫技术可以用于收集游戏数据、用户行为等信息，为游戏运营提供有力支持。同时，通过分析玩家反馈、游戏流行趋势，游戏开发者可以及时优化产品，提高用户满意度。网络安全：保障跨界电商与......
  • 什么是Overlay网络？Overlay网络与Underlay网络有什么区别？
    你们好，我的网工朋友。在传统历史阶段，数据中心的网络是以三层架构（核心、汇聚、接入）为基本标准。但是随着技术的发展，不同的厂家有不同的组建方式，比如说在核心层、汇聚层和接入层增加虚拟化技术。不管怎么改变，都没有改变以太网络传输的基本原则，都是需要靠网络地址、物理地址来进行控制......
  • VMware 虚拟机的三种网络工作模式
    目录介绍桥接模式桥接模式网络设置NAT模式实际操作中注意事项Host-Only介绍vmware为我们提供了三种网络工作模式,它们分别是:Bridged（桥接模式）、NAT（网络地址转换模式）、Host-Only（仅主机模式）。默认情况下，当安装完VMware虚拟机软件时，进入vmware,在选项栏的"编辑"下的"虚拟网络......
  • swift网络框架配置(三)
    1.WMGetApiManager(get请求)importUIKitimportMoyaenumWMGetApiManager{//获取配置caseappConfig//获取app信息casegetAppInfo(phone:String)}extensionWMGetApiManager:TargetType{varbaseURL:URL{switchself{......
  • swift网络框架配置(二)
    1.WMPostApiManager（post请求）importMoyaenumWMPostApiManager{//登录caselogin(login_type:String,id:String,password:String)}extensionWMPostApiManager:TargetType{varbaseURL:URL{returnURL(string:"https://api......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99