首页 > 代码库 > 最大流当前弧优化Dinic分层模板
最大流当前弧优化Dinic分层模板
最大流模板：
- 普通最大流
- 无向图限制：将无向图的边拆成2条方向相反的边
- 顶点有流量限制：拆成2个点，连接一条容量为点容量限制的边
- 无源汇点有最小流限制的最大流：理解为水管流量形成循环，每根水管有流量限制，并且流入量等于流出量
- 有源汇点的最小流限制的最大流
- 有最小流量限制的最小流
- 容量为负数：不能直接利用最大流求边权为负数的最小割。不知道怎么具体处理。。。
模板使用Dinic分层算法，使用了当前弧优化，效率还是不错的，使用的是vector存图，如果使用邻接表存图效率应该会高一些些吧。
但是ispa算法的效率更高，采用了当前弧优化的ispa算法那就更更高的效率了(=^ ^=)，但是这个算法目前不会啊。。。
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<set>#include<map>#include<queue>#include<stack>#include<vector>using namespace std;typedef long long ll;typedef pair<int,int> P;#define PI acos(-1.0)const int maxn=1e5+100,maxm=1e5+100,inf=0x3f3f3f3f,mod=1e9+7;const ll INF=1e18+7;struct edge{ int from,to,cap,flow;};struct Dinic{ int n,m,s,t; vector<edge>es; vector<int>G[maxn]; bool vis[maxn]; int dist[maxn],iter[maxn]; void init(int n,int m) { this->n=n; this->m=m; for(int i=0; i<=n+5; i++) G[i].clear(); es.clear(); } void addedge(int from,int to,int cap) { es.push_back((edge) { from,to,cap,0 }); es.push_back((edge) { to,from,0,0 }); int x=es.size(); G[from].push_back(x-2); G[to].push_back(x-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue <int> Q; vis[s]=1; dist[s]=0; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); for (int i=0; i<G[u].size(); i++) { edge &e=es[G[u][i]]; if (!vis[e.to]&&e.cap>e.flow) { vis[e.to]=1; dist[e.to]=dist[u]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int u,int f) { if(u==t||f==0) return f; int flow=0,d; for(int &i=iter[u]; i<G[u].size(); i++) { edge &e=es[G[u][i]]; if(dist[u]+1==dist[e.to]&&(d=DFS(e.to,min(f,e.cap-e.flow)))>0) { e.flow+=d; es[G[u][i]^1].flow-=d; flow+=d; f-=d; if (f==0) break; } } return flow; } int Maxflow(int s,int t) { this->s=s,this->t=t; int flow=0; while(BFS()) { memset(iter,0,sizeof(iter)); flow+=DFS(s,inf); } return flow; }} Dinc;int in[maxn],out[maxn];int sign[maxn];int main(){ int n,m; scanf("%d%d",&n,&m); /**有源汇点*/ int s,t; scanf("%d%d",&s,&t); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); Dinc.init(n,m); for (int i=1; i<=m; i++) { int u,v,l,r; scanf("%d %d %d %d",&u,&v,&l,&r); out[u]+=l; in[v]+=l; sign[i]=l; Dinc.addedge(u,v,r-l); } /**最小流限制有源汇点*/ Dinc.addedge(t,s,inf);
/**最小流限制，新增源点0，汇点n+1*/ int all=0,sum=0; for(int i=1; i<=n; i++) { if(in[i]>out[i]) { Dinc.addedge(0,i,in[i]-out[i]); all+=in[i]-out[i]; } else if(in[i]<out[i]) { Dinc.addedge(i,n+1,out[i]-in[i]); sum+=(in[i]-out[i]); } } if(Dinc.Maxflow(0,n+1)!=all) puts("NO"); else { puts("YES"); /**有源汇点*/ sum=-Dinc.es[2*m+1].flow; Dinc.es[2*m+1].flow=0; Dinc.es[2*m].flow=0; Dinc.es[2*m].cap=0; sum+=Dinc.Maxflow(s,t); printf("%d\n",sum); /**无源汇点：可以理解成水管相连，每根水管的水流入量等于流出量，所有水管形成循环*/ for(int i=0; i<m*2; i+=2) printf("%d\n",Dinc.es[i].flow+sign[i/2+1]);///每根水管的流量情况 } return 0;}
最大流当前弧优化Dinic分层模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。