网络流模板

发布时间:2017-6-27 17:00:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"网络流模板",主要涉及到网络流模板方面的内容,对于网络流模板感兴趣的同学可以参考一下。

Isap模板: const int maxn=20100; const int maxm=1002000; struct Edge{ int next,to,cap; Edge(){}; Edge(int _next,int _to,int _cap){ next=_next;to=_to;cap=_cap; } }edge[maxm]; int head[maxn],tol,dep[maxn],gap[maxn]; void addedge(int u,int v,int flow){ edge[tol]=Edge(head[u],v,flow);head[u]=tol++; edge[tol]=Edge(head[v],u,0);head[v]=tol++; } void bfs(int start,int end){ memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]++;int front=0,rear=0,Q[maxn]; dep[end]=0;Q[rear++]=end; while(front!=rear){ int u=Q[front++]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to;if(dep[v]==-1) Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++; } } } int sap(int s,int t,int N){ int res=0;bfs(s,t); int cur[maxn],S[maxn],top=0,u=s,i; memcpy(cur,head,sizeof(head)); while(dep[s]<N){ if(u==t){ int temp=INF,id; for( i=0;i<top;i++) if(temp>edge[S[i]].cap) temp=edge[S[i]].cap,id=i; for( i=0;i<top;i++) edge[S[i]].cap-=temp,edge[S[i]^1].cap+=temp; res+=temp;top=id;u=edge[S[top]^1].to; } if(u!=t&&gap[dep[u]-1]==0)break; for( i=cur[u];i!=-1;i=edge[i].next) if(edge[i].cap&&dep[u]==dep[edge[i].to]+1)break; if(i!=-1)cur[u]=i,S[top++]=i,u=edge[i].to; else{ int MIN=N; for( i=head[u];i!=-1;i=edge[i].next) if(edge[i].cap&&MIN>dep[edge[i].to]) MIN=dep[edge[i].to],cur[u]=i; --gap[dep[u]];++gap[dep[u]=MIN+1]; if(u!=s)u=edge[S[--top]^1].to; } } return res; } dinic模板: const int maxn=1110; const int maxm=400010; struct Edge{ int to,next,cap; Edge(){}; Edge(int _next,int _to,int _cap){ next=_next;to=_to;cap=_cap; } }edge[maxm]; int head[maxn],tol,dep[maxn],cur[maxn],n; void addedge(int u,int v,int flow){ edge[tol]=Edge(head[u],v,flow);head[u]=tol++; edge[tol]=Edge(head[v],u,0);head[v]=tol++; } int Q[maxn]; bool bfs(int start,int end){ memset(dep,-1,sizeof(dep)); int front=0,rear=0; dep[start]=0;Q[rear++]=start; while(front!=rear){ int u=Q[front++]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to;if(dep[v]==-1&&edge[i].cap){ Q[rear++]=v,dep[v]=dep[u]+1; if(v==end)return 1; } } } return 0; } int dinic(int s,int t){ int i,res=0,top; int S[maxn],cur[maxn]; while(bfs(s,t)){ memcpy(cur,head,sizeof(head)); int u=s;top=0; while(1){ if(u==t){ int min=INF,loc; for(int i=0;i<top;i++)if(min>edge[S[i]].cap) min=edge[S[i]].cap,loc=i; for(int i=0;i<top;i++) edge[S[i]].cap-=min,edge[S[i]^1].cap+=min; res+=min;top=loc;u=edge[S[top]^1].to; } for(int i=cur[u];i!=-1;cur[u]=i=edge[i].next) if(edge[i].cap&&dep[u]+1==dep[edge[i].to])break; if(cur[u]!=-1)S[top++]=cur[u],u=edge[cur[u]].to; else{ if(top==0)break; dep[u]=-1;u=edge[S[--top]^1].to; } } } return res; } 最小费用最大流模板: const int maxn=300; const int maxm=3000000; struct node{ int next,to,cap,cost; node(){}; node(int _next,int _to,int _cap,int _cost){ next=_next;to=_to;cap=_cap;cost=_cost; } }edge[maxm]; int head[maxn],vis[maxn],pre[maxn],dis[maxn],n,tol; void addedge(int u,int v,int cap,int cost){ edge[tol]=node(head[u],v,cap,cost);head[u]=tol++; edge[tol]=node(head[v],u,0,-cost);head[v]=tol++; } bool spfa(int s,int t){ queue<int> q; for(int i=0;i<=n+1;i++) dis[i]=INF,vis[i]=0,pre[i]=-1; dis[s]=0;vis[s]=1;q.push(s); while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(edge[i].cap&&dis[v]>dis[u]+edge[i].cost){ dis[v]=dis[u]+edge[i].cost;pre[v]=i; if(!vis[v])vis[v]=1,q.push(v); } } } if(pre[t]==-1)return 0; return 1; } int fun(int s,int t,int &flow,int &cost){ while(spfa(s,t)){ int MIN=INF; for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]) if(MIN>edge[i].cap)MIN=edge[i].cap; for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]) edge[i].cap-=MIN,edge[i^1].cap+=MIN,cost+=edge[i].cost*MIN; flow+=MIN; } return cost; }

上一篇:this
下一篇:WinXP环境下VS2010配置Cocos2d-x-2.1.4最新版本的开发环境

相关文章

关键词: 网络流模板

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。