struct sap{
typedef int type;
struct edge{
int to,next;
type flow;
}edg[999999];//边表
int n,m;//顶点数,边数
int g[M],cur[M],pre[M];//邻接表,当前弧,上一个点
int dis[M],gap[M];//层次数组,间隙优化
int q[M],head,tail;//队列
void init(int _n){n=_n,m=0,clr_all(g,-1);}//初始化
void insert(int u,int v,type f,type c=0){//插边
edg[m].to=v,edg[m].flow=f,edg[m].next=g[u],g[u]=m++;
edg[m].to=u,edg[m].flow=0,edg[m].next=g[v],g[v]=m++;
}
bool bfs(int s,int t){//反向广搜,初始化层次数组
clr(gap,0,n),clr(dis,-1,n);
gap[dis[t]=0]++,dis[s]=-1;
for(q[head=tail=0]=t;head<=tail;){
int u=q[head++];
for(int i=g[u];i!=-1;i=edg[i].next){
edge& e=edg[i],ee=edg[i^1];
if(dis[e.to]==-1 && ee.flow>0){
gap[dis[e.to]=dis[u]+1]++;
q[++tail]=e.to;
}
}
}
return dis[s]!=-1;
}
type maxFlow(int s,int t){//求最大流
if(!bfs(s,t)) return 0;
type res=0,a;
int i;
for(i=0;i<n;i++) cur[i]=g[i];
pre[s]=s,cur[s]=g[s],cur[t]=g[t];
for(int u=s;dis[s]<n;){
if(u==t){//增广
for(a=-1;u!=s;u=pre[u])
getmin(a,edg[cur[pre[u]]].flow);
for(u=t;u!=s;u=pre[u]){
edg[cur[pre[u]]].flow-=a;
edg[cur[pre[u]]^1].flow+=a;
}
res+=a;
}
bool ok=0;//当前增广路是否能前推的标志,0否,1是
for(i=cur[u];i!=-1;i=edg[i].next){//前推
edge& e=edg[i];
if(dis[u]==dis[e.to]+1 && e.flow>0){
cur[u]=i,pre[e.to]=u,u=e.to;
ok=1;break;
}
}
if(ok) continue;
int mindis=n-1;
for(i=g[u];i!=-1;i=edg[i].next){//当前增光路不能前推,回退
edge& e=edg[i];
if(mindis>dis[e.to] && e.flow>0)
mindis=dis[e.to],cur[u]=i;
}
if(--gap[dis[u]]==0) break;//出现断层,当前流是最大流
gap[dis[u]=mindis+1]++,u=pre[u];
}
return res;
}
};
分享到:
相关推荐
BFS++ 是西门子一个优秀的资产管理软件。主要应用于电厂等大型资产密集型企业。
BFS++是以网络为支撑、数据库为核心,以设备的运行和维修管理为主要对象的一套综合性的电厂生产管理系统。它提供的主要功能包括:基本系统、设备数据、维修管理、运行管理、备件管理、文档管理等六个部分。
图的相关算法比较全面的总结,包括了图的深度和广度遍历算法,prim和kruskal两种最小生成树的算法,邻接矩阵和邻接表两种储存结构,做课程设计、实验报告或者数据结构学习者可以参考参考啊``源代码都是我亲手打的,...
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
ACM入门题,BFS + hash 的使用与结合
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
this is code for bfs in c++
bfs ,dfs algoritm in TC
邻接表存储的图的DFS,BFS遍历。文档描述: http://blog.csdn.net/qq_16912257/article/details/45848935
头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
基于邻接表存储的图的dfs与bfs遍历,对学习数据结构很有帮助
用邻接矩阵来存储图,Floyed算法求任意两点间的最短路径并输出,广度优先遍历,深度优先遍历
/* 邻接表的结点类型 */ typedef struct arc {int adjvex; struct arc *next;}ArcNode; typedef struct VexNode {int vertex; ArcNode *firstarc; }VerNode; typedef VerNode AdjList[MAXNODE]; /* 建立图...
程序用交互方式完成图的邻接矩阵和邻接表的构造,并提供了DFS和BFS算法。
用字符文件提供数据建立连通无向图邻接表存储结构。编写程序,实现DFS与BFS算法,输出DFS与BFS生成树的每条边。(边用顶点序号组成的无序偶表示) 实验目的:掌握图的邻接表存储结构;掌握图的遍历算法与生成树。
分别以邻接矩阵和邻接表的方式实现图的深度优先搜索、广度优先搜索
邻接表深度广度优先搜索测试程序
假设图中各边的权值都相等,以邻接矩阵和邻接表为存储结构,分别写出算法: (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径 要求输出路径上的所有顶点(利用BFS遍历的思想)
最终效果是实现了Prim随机生成迷宫,BFS&DFS路径显示、最短路长度显示、过程动态展示,主函数中有菜单,操作方便。 不仅可以用来读代码长知识、还可以用作算法演示。 附带第五版的exe文件,欢迎使用!
1.包含了8个文档。 2.大部分为集训队文档。 3.部分算法详解文档。 4.文库搜索,全部下载需要十几分。