当前位置: 首页 > news >正文

网络流

对于普通的网络流算法,感觉就是很暴力的寻找增广路,而增广路,就是路径边权最小值最大的一条路径。

网络流的特殊之处,认为就是对反向边的处理,它做了一个负边权的处理,使得有反悔的余地。

这一部分的参考。

残量网络:所有剩余容量不为 \(0\) 的边构成的子图叫做原图的残量网络。

最大流:对每条边加入流量,从源点发出的最大流量值。

Edmonds−Karp 增广路算法

增广路:一条从源点到汇点上的所有边剩余容量均不为 \(0\) 的路径。

考虑找增广路的过程,因为最大流可以认为是每条增广路流量的叠加,所以寻找增广路的顺序是不必要的,只要每一次能找到即可。

对于反向边的存储,建议使用链式前向星,因为 vector 写起来好像有点麻烦,从 tot=1 开始存储,对于反向边就是 i^1

因此,我们只需要每一个暴力 \(O(nm)\) 寻找增广路就好了,期望时间复杂度 \(O(nm^2)\)

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar('\n')
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define pdi pair<ll,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(register ll i = a ; i <= b ; ++ i )
#define Fo(a,i,b) for(register ll i = a ; i >= b ; -- i )
#define pb push_back
//#define pis pair<ll,char >
//#pragma GCC optimize(2)
using namespace std;
//typedef int ll;
typedef long long ll;
//typedef __int128 ll;
typedef double db;
inline void read(ll &opp){ll x=0,t=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){t=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}opp=x*t;return; }
inline void wr(ll x){if(x<0){putchar('-');x=-x;}if(x>9){wr(x/10);}putchar(x%10+'0');}
const ll N=3e5+5,M=5e6,mod=998244353;
ll n,m,s,t,tot=1,head[N],ans,vis[N],dis[N],pre[N],f[2005][2005];
struct Edge{ll ver,nxt,w;}g[N];
inline void add(ll x,ll y,ll w){g[++tot].ver=y,g[tot].nxt=head[x];g[tot].w=w;head[x]=tot;} 
inline ll bfs()
{fo(0,i,n+1) vis[i]=0;queue<ll> q;q.push(s);dis[s]=inf;vis[s]=1;while(!q.empty()){ll x=q.front();q.pop();for(ll i=head[x];i;i=g[i].nxt){ll y=g[i].ver,w=g[i].w;if(vis[y]||!w) continue;vis[y]=1;dis[y]=min(dis[x],w);q.push(y);pre[y]=i;if(y==t) return 1;}}return 0;
}
inline void check()
{ll now=t;ans+=dis[t];while(now!=s) g[pre[now]].w-=dis[t],g[pre[now]^1].w+=dis[t],now=g[pre[now]^1].ver;
}
signed main(){read(n),read(m),read(s),read(t);ll u,v,w;fo(1,i,m){read(u),read(v),read(w);if(!f[u][v]) add(u,v,w),add(v,u,0),f[u][v]=tot-1;else g[f[u][v]].w+=w;}while(bfs()) check();wr(ans),pr;return 0;
}

Dinic 算法

Dinic 是可以一次找到多条增广路的算法,我们先做一次 bfs 建出分层图,或者称为可能的增广路图,这个分层图显然是个 DAG,我们在这上面跑 dfs,每次动态更新流量,就能做到一次尽可能找到多条增广路了。

Dinic 中用到两个优化,当前弧优化和剪枝,感觉就是名字高大上啊我去,感觉很朴素啊。

  • 当前弧优化,就是对于当前算到这个点的第 \(i\) 条边,显然前面 \(i-1\) 条边的增广路径早就算完了,所以每次从 \(i\) 开始算就好了,注意每一次增广的当前弧是重置的。

  • 剪枝,每次把增广完毕的点删掉就好了。

复杂度 \(O(n^2m)\),比 EK 优得多,实际根本跑不满。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar('\n')
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define pdi pair<ll,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(register ll i = a ; i <= b ; ++ i )
#define Fo(a,i,b) for(register ll i = a ; i >= b ; -- i )
#define pb push_back
//#define pis pair<ll,char >
//#pragma GCC optimize(2)
using namespace std;
//typedef int ll;
typedef long long ll;
//typedef __int128 ll;
typedef double db;
inline void read(ll &opp){ll x=0,t=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){t=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}opp=x*t;return; }
inline void wr(ll x){if(x<0){putchar('-');x=-x;}if(x>9){wr(x/10);}putchar(x%10+'0');}
const ll N=3e5+5,M=5e6,mod=998244353;
ll n,m,s,t,tot=1,head[N],ans,vis[N],dis[N],pre[N],now[N];
struct Edge{ll ver,nxt,w;}g[N];
inline void add(ll x,ll y,ll w){g[++tot].ver=y,g[tot].nxt=head[x];g[tot].w=w;head[x]=tot;} 
inline ll bfs()
{fo(0,i,n+1) dis[i]=inf;queue<ll> q;q.push(s);dis[s]=0;now[s]=head[s];while(!q.empty()){ll x=q.front();q.pop();for(ll i=head[x];i;i=g[i].nxt){ll y=g[i].ver,w=g[i].w;if(w>0&&dis[y]==inf){dis[y]=dis[x]+1;now[y]=head[y];q.push(y);if(y==t) return 1;}}}return 0;
}
inline ll dfs(ll x,ll sum)
{if(x==t) return sum;ll k,res=0;for(ll i=now[x];i;i=g[i].nxt){ll y=g[i].ver,w=g[i].w;now[x]=i;if(w<=0||dis[y]!=dis[x]+1) continue;k=dfs(y,min(sum,w));if(!k) dis[y]=inf;g[i].w-=k,g[i^1].w+=k;res+=k,sum-=k;}return res;
}
signed main(){read(n),read(m),read(s),read(t);ll u,v,w;fo(1,i,m){read(u),read(v),read(w);add(u,v,w),add(v,u,0);}while(bfs()) ans+=dfs(s,inf);wr(ans),pr;return 0;
}
http://www.hskmm.com/?act=detail&tid=12076

相关文章:

  • 完整教程:数据结构 栈和队列、树
  • 深入解析:【ubuntu】ubuntu中找不到串口设备问题排查
  • 酵母双杂交技术:高通量筛选的突破与不可忽视的三大局限性
  • ubuntu20.04测试cuda
  • Android Studio 配置国内源
  • PyCharm项目上传GitHub仓库(笔记) - 教程
  • 从RAG出发
  • 软件工程第二次作业——第一次个人编程作业
  • Ubuntu 24.04 安装 DaVinci Resolve
  • Promise中处理请求超时问题
  • 图解26:老生常谈的OSI网络模型
  • 【C++】指针
  • AI驱动建筑行业数字化转型
  • 详细介绍:前端学习——CSS
  • VSCode 把代码发送到激活状态下的终端
  • 线性结构之数组[基于郝斌课程]
  • 完整教程:Vue中的props方式
  • 图解25:MySQL主从复制原理
  • 用 Go 编写验证码识别脚本(基于 Tesseract)
  • 软工第二次作业
  • Zero-Shot、One-Shot、Few-Shot概念
  • ADS放入元器件include和DK.zip文件依然提示未定义
  • AI元人文(十三):良知觉醒——论三值伦理模型与元道德主体的诞生
  • 「MCOI-05」魔仙
  • BlueHat v18 会议资料现已发布:前沿安全技术与漏洞缓解策略
  • label和brand的区别(品牌=brand?错了,你们的英语都学错了!)
  • 2025.9.21——1绿
  • 故障处理:ORA-04031真实案例分享
  • 图解24:8种常用的缓存淘汰策略
  • 读书笔记:更智能的数据库索引:只关注你需要的数据