文章目录

参考博客：最大流模板：$Dinic：$$ISAP：$$HLPP：$ 最小费用最大流：割与最小割：建模技巧选讲多源多汇无向图顶点也有流量限制最大权闭合子图区间$k$次覆盖

参考博客：

网络流基础知识及经典算法(这个内容比较详细 虽然有一些重复的知识点？) 最大流、费用流基础知识(这个比较简短 而且有残余网络的图示 可以结合上面那个一起学习 加深理解 不过它的图$1$有个地方写错了~) $Dinic$的当前弧优化 $ISAP与HLPP$ $HLPP$ $HLPP$ 最大流最小割

最大流模板：

$Dinic：$

复杂度上限为$O(n^{2}m)$，不过这个上限比较松。

#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; //Dinic模板 除了顶点数和变数 基本不需要改动什么 const int maxn=1e4+5; const int maxm=1e5+5; struct Edge { int to,nxt,f; }; //前向星存边 Edge edge[maxm<<1]; //边的空间至少要开两倍 因为有反向边的存在 int head[maxn],cur[maxn];//cur用于当前弧优化 int tot=1; //边的编号 int depth[maxn]; //用于bfs分层 int n,m,s,t; //定点数 边数 源点 汇点 inline void addedge(int u,int v,int dis) //加一条 u->v 容量为dis的边 那么自然要加一条 v->u 流量为0的反向边 { edge[++tot].to=v,edge[tot].f=dis; edge[tot].nxt=head[u]; head[u]=tot; edge[++tot].to=u,edge[tot].f=0; edge[tot].nxt=head[v]; head[v]=tot; } bool bfs() //bfs分层 { memcpy(cur,head,sizeof(cur));//当前弧优化要用到 memset(depth,0,sizeof(depth));//初始化为0或-1均可 看个人习惯 queue<int> q; depth[s]=1; //源点 q.push(s); int fir,to; while(!q.empty()) { fir=q.front(); q.pop(); for(int i=head[fir];i;i=edge[i].nxt) { to=edge[i].to; if(edge[i].f&&!depth[to]) //对于前向边来说 该边的流量未满 对于后向边来说 该边有流量可退回 { depth[to]=depth[fir]+1; q.push(to); } } } return depth[t]; } //dfs 寻找多条增广路 int dfs(int u,int lim)//当前节点 当前流量 { if(u==t)//汇点 return lim; int v,temp,ans=0; for(int i=cur[u];i;i=edge[i].nxt) { cur[u]=i; //当前弧优化 v=edge[i].to; if(depth[v]==depth[u]+1&&edge[i].f) { temp=dfs(v,min(lim,edge[i].f)); edge[i].f-=temp; edge[i^1].f+=temp; ans+=temp; lim-=temp; //多路增广 EK算法在此处已经return了 if(!lim) //流入当前节点的流量已经用完了 就没必要继续寻找增广路了 break; } } if(lim||!ans) //流没用完 或者该点对答案没有任何贡献 以后也没必要访问该点 depth[u]=0; return ans; } int dinic() { int ans=0; //答案 while(bfs()) //分层 ans+=dfs(s,INF); //dfs找增广路 return ans; } int main() { while(~scanf("%d %d %d %d",&n,&m,&s,&t)) { memset(head,0,sizeof(head)); tot=1; int u,v,c; for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); } printf("%d\n",dinic()); } return 0; }

$ISAP：$

只进行$1$次$bfs$，复杂度更加优秀！

#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; //ISAP模板 除了需要改变顶点数和边数 //还要改变 isap() 函数中循环体的判断 //和 dfs() 对depth数组的更改 const int maxn=1e4+5; const int maxm=1e5+5; struct Edge { int to,nxt,f; }; //前向星存边 Edge edge[maxm<<1]; //边的空间至少要开两倍 因为有反向边的存在 int head[maxn],cur[maxn];//cur用于当前弧优化 int tot=1; //边的编号 int depth[maxn],cnt[maxn]; int n,m,s,t; //定点数 边数 源点 汇点 inline void addedge(int u,int v,int dis) //加一条 u->v 容量为dis的边 那么自然要加一条 v->u 流量为0的反向边 { edge[++tot].to=v,edge[tot].f=dis; edge[tot].nxt=head[u]; head[u]=tot; edge[++tot].to=u,edge[tot].f=0; edge[tot].nxt=head[v]; head[v]=tot; } void bfs() //bfs处理出深度 { memset(depth,0,sizeof(depth)); memset(cnt,0,sizeof(cnt)); queue<int> q; //注意 此处是从汇点开始 depth[t]=1,cnt[1]=1; //汇点 q.push(t); int fir,to; while(!q.empty()) { fir=q.front(); q.pop(); for(int i=head[fir];i;i=edge[i].nxt) { to=edge[i].to; if(edge[i].f&&!depth[to]) { depth[to]=depth[fir]+1; ++cnt[depth[to]]; q.push(to); } } } } int dfs(int u,int lim)//当前节点 当前流量 { if(u==t)//汇点 return lim; int v,temp,ans=0; for(int i=cur[u];i;i=edge[i].nxt) { cur[u]=i; //当前弧优化 v=edge[i].to; if(depth[v]==depth[u]-1&&edge[i].f) { temp=dfs(v,min(lim,edge[i].f)); edge[i].f-=temp; edge[i^1].f+=temp; ans+=temp; lim-=temp; //多路增广 if(!lim) //流入当前节点的流量已经用完了 就没必要继续寻找增广路了 break; } } if(lim||!ans) //流没用完 或者该点对答案没用任何贡献 { if(--cnt[depth[u]]==0) depth[s]=n+1; ++cnt[++depth[u]]; } return ans; } int isap() { int ans=0; //答案 bfs(); while(depth[s]<=n) //分层 此处视 顶点个数 不同需要改变 { memcpy(cur,head,sizeof(cur)); ans+=dfs(s,INF); //dfs找增广路 } return ans; } int main() { while(~scanf("%d %d %d %d",&n,&m,&s,&t)) { memset(head,0,sizeof(head)); tot=1; int u,v,c; for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); } printf("%d\n",isap()); } return 0; }

$HLPP：$

时间复杂度$O(n^2\sqrt{m})$，不过这个上限比较紧，一般来说$Dinic$和$ISAP$就够了，除非毒瘤出题人卡了前两个算法。

#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int maxn=2e3+5; const int maxm=2e5+5; struct Edge { int to,nxt,f; }edge[maxm<<1]; int n,m,s,t,tot; int head[maxn],depth[maxn],rest[maxn],inque[maxn],cnt[maxn<<1]; struct cmp { inline bool operator ()(int a,int b)const { return depth[a]<depth[b]; } }; priority_queue<int,vector<int>,cmp> q; inline int read() //注意 该快读省去了负数的情况 { char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); int ans=0; while(ch>='0'&&ch<='9') { ans=(ans<<3)+(ans<<1)+ch-48; ch=getchar(); } return ans; } inline void addedge(int u,int v,int dis) { edge[++tot].to=v,edge[tot].f=dis; edge[tot].nxt=head[u]; head[u]=tot; edge[++tot].to=u,edge[tot].f=0; edge[tot].nxt=head[v]; head[v]=tot; } void bfs() { queue<int> que; memset(cnt,0,sizeof(cnt)); memset(depth,0,sizeof(depth)); depth[t]=1,cnt[1]=1; que.push(t); while(!que.empty()) { int u=que.front(); que.pop(); for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(!depth[v]) { depth[v]=depth[u]+1; ++cnt[depth[v]]; que.push(v); } } } } inline void out(int u)//推流 { int flow; for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(edge[i].f&&depth[u]==depth[v]+1) { flow=min(edge[i].f,rest[u]); //边的流量 u点的余流 edge[i].f-=flow; edge[i^1].f+=flow; rest[u]-=flow; rest[v]+=flow; if(v!=s&&v!=t&&!inque[v])//如果v不是源点不是汇点且不在优先队列中则入队 q.push(v),inque[v]=1; if(!rest[u]) //节点u 已没有余流可推 break; } } return ; } inline void relable(int u)//修改深度 { depth[u]=INF; for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(edge[i].f&&depth[v]+1<depth[u]) depth[u]=depth[v]+1; } return ; } int hlpp() { bfs(); if(depth[s]==0) //可以判断一下连通性 return 0; depth[s]=n; memset(rest,0,sizeof(rest)); memset(inque,0,sizeof(inque)); for(int i=head[s];i;i=edge[i].nxt)//源点s向 邻接点推流 { int u=edge[i].to; if(edge[i].f) { rest[u]+=edge[i].f; swap(edge[i].f,edge[i^1].f); if(u!=s&&u!=t&&!inque[u]) q.push(u),inque[u]=1; } } while(!q.empty()) //按照高度 依次推流 { int u=q.top(); q.pop(); inque[u]=0; out(u); //推流 if(rest[u]) { if(--cnt[depth[u]]==0) { for(int i=1;i<=n;i++) if(i!=s&&i!=t&&depth[i]>depth[u]&&depth[i]<=n) depth[i]=n+1; } relable(u); ++cnt[depth[u]]; q.push(u); inque[u]=1; } } return rest[t]; } int main() { while(~scanf("%d %d %d %d",&n,&m,&s,&t)) { tot=1; memset(head,0,sizeof(head)); int u,v,w; for(int i=0;i<m;i++) { u=read(),v=read(),w=read(); // scanf("%d %d %d",&u,&v,&w); addedge(u,v,w); } printf("%d\n",hlpp()); } }

最小费用最大流：

$SPFA$版本：

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define INF 0x3f3f3f3f using namespace std; const int maxn=5005; const int maxm=50005; struct Edge { int to,nxt,f,w; }edge[maxm<<1]; int n,m,s,t,tot; int head[maxn]; //前向星 int dis[maxn],pre[maxn],maxf[maxn],inque[maxn];//dis用于最短路 pre记录前驱边 maxf记录最小剩余容量 inque记录是否在队列中 inline void addedge(int u,int v,int c,int w)//容量为c 权值为w { edge[++tot].to=v,edge[tot].f=c,edge[tot].w=w,edge[tot].nxt=head[u],head[u]=tot; edge[++tot].to=u,edge[tot].f=0,edge[tot].w=-w,edge[tot].nxt=head[v],head[v]=tot; } bool spfa() { queue<int> q; q.push(s); memset(dis,INF,sizeof(dis)); dis[s]=0,inque[s]=1,maxf[s]=INF;//源点流量无限大 while(!q.empty()) { int u=q.front(); q.pop(),inque[u]=0;; for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(edge[i].f&&dis[u]+edge[i].w<dis[v]) { dis[v]=dis[u]+edge[i].w; pre[v]=i; //记录前驱边 maxf[v]=min(maxf[u],edge[i].f);//流入v的流量等于 二者的最小值 if(!inque[v]) inque[v]=1,q.push(v); } } } if(dis[t]<INF) return 1; return 0; } void MCMF() { int mflow=0,mcost=0; while(spfa()) { int u=t,v; while(u!=s) { v=pre[u]; edge[v].f-=maxf[t]; edge[v^1].f+=maxf[t]; u=edge[v^1].to; } mflow+=maxf[t]; mcost+=dis[t]*maxf[t]; } printf("%d %d\n",mflow,mcost); } int main() { while(~scanf("%d%d%d%d",&n,&m,&s,&t)) { tot=1; memset(head,0,sizeof(head)); int u,v,f,w; for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u,&v,&f,&w); addedge(u,v,f,w); } MCMF(); } }

割与最小割：

还是不懂割是什么？看图： 如果是求割点怎么办？（转自洛谷）

建模技巧选讲

多源多汇

无向图

顶点也有流量限制

最大权闭合子图

$update：$有一处笔误，应该是源点向正权点连边，负权点向汇点连容量为其权值绝对值的边。 结论就是最大权闭合子图的权值=子图内正权值之和-最小割 证明如下：

区间$k$次覆盖

坐标过大的话需要离散化。