阿里云域名注册好了怎么做网站,建网站需要哪些硬件,安徽设计网站建设,网站租房做公寓题意#xff1a;1是源点#xff0c;m是汇点#xff0c;求出来最大流量#xff0c;没什么好说的就是练习最大流的模板题 ************************************************************** 先用Edmonds-Karp的算法做一下试试吧重边贡献了 1W#xff0c;要加上所有的重边才算…题意1是源点m是汇点求出来最大流量没什么好说的就是练习最大流的模板题 ************************************************************** 先用Edmonds-Karp的算法做一下试试吧重边贡献了 1W要加上所有的重边才算是两点间最大流量 *********************************************************************************************************************** /************************************//** 使用Edmonds-Karp 最短增广路算法*//** 邻接矩阵实现 *//** 2015/8/7/9:39 *//************************************/#includestdio.h#includestring.h#includequeue#includealgorithmusing namespace std;const int MAXN 205;const int oo 1e97;///1是源点M是汇点N条边int G[MAXN][MAXN], M, N;int pre[MAXN];///记录每个点的前驱也就是父节点bool used[MAXN];///s代表源点e代表汇点,可以到达汇返回true否则返回falsebool BFS(int s, int e){ memset(used, false, sizeof(used)); queueint Q; Q.push(s); used[s] true; while(Q.size()) { s Q.front();Q.pop(); if(s e) return true; for(int i1; iM; i) { if(G[s][i] !used[i]) { pre[i] s; used[i] true; Q.push(i); } } } return false;}int Karp(int s, int e){ int MaxFlow 0; while( BFS(s, e) true ) {///如果有增量 int MinFlow oo, v; v e; while(v ! s) {///求出来路径上最小流量 MinFlow min(MinFlow, G[pre[v]][v]); v pre[v]; } MaxFlow MinFlow; v e; while(v ! s) {///边上的所有点减去最小流量反边增加流量 G[pre[v]][v] - MinFlow; G[v][pre[v]] MinFlow; v pre[v]; } } return MaxFlow;}int main(){ while(scanf(%d%d, N, M) ! EOF) { int i, u, v, c; memset(G, false, sizeof(G)); for(i1; iN; i) { scanf(%d%d%d, u, v, c); G[u][v] c;///有重边两点间应该算上所有边 } printf(%d\n, Karp(1, M)); } return 0;} View Code 邻接表实现 *********************************************************************************************************************** /************************************//// 使用Edmonds-Karp 最短增广路算法/// 邻接表实现/// 2015年8月7日10:13:55/************************************/#includestdio.h#includestring.h#includequeue#includealgorithmusing namespace std;const int MAXN 205;const int oo 1e97;struct Edge{int u, v, Flow, next;}e[MAXN1];int Head[MAXN], cnt;int pre[MAXN], used[MAXN];void InIt(){ memset(Head, -1, sizeof(Head)); cnt 0;}void AddEdge(int u, int v, int Flow){ e[cnt].u u; e[cnt].v v; e[cnt].Flow Flow; e[cnt].next Head[u]; Head[u] cnt;}bool BFS(int s, int End){ memset(used, false, sizeof(used)); memset(pre, -1, sizeof(pre)); queueint Q; Q.push(s); used[s] true; while(Q.size()) { s Q.front();Q.pop(); if(s End)return true; for(int iHead[s]; i!-1; ie[i].next) { if(e[i].Flow used[e[i].v] false) { used[e[i].v] true; pre[e[i].v] i;///记录的是上面的边的位置 Q.push(e[i].v); } } } return false;}int Karp(int s, int End){ int MaxFlow 0; while(BFS(s, End) true) { int MinFlow oo, v; v pre[End]; while(v ! -1) { MinFlow min(MinFlow, e[v].Flow); v pre[e[v].u];///上个点来的位置 } MaxFlow MinFlow; v pre[End]; while(v ! -1) { e[v].Flow - MinFlow; e[v^1].Flow MinFlow; v pre[e[v].u]; } } return MaxFlow;}int main(){ int N, M; while(scanf(%d%d, N, M) ! EOF) { int i, u, v, Flow; InIt(); for(i1; iN; i) { scanf(%d%d%d, u, v, Flow); AddEdge(u, v, Flow); AddEdge(v, u, 0);///先添加一条反边的流量是0 } printf(%d\n, Karp(1, M)); } return 0;} code Dinic实现 ************************************************************************************************************************ #includestdio.h#includestring.h#includequeueusing namespace std;const int MAXN 205;const int oo 1e97;struct Edge{int u, v, flow, next;}edge[MAXN*MAXN];int Head[MAXN], cnt;int layer[MAXN];///分层int Start, End;///源点汇点void AddEdge(int u, int v, int flow){ edge[cnt].u u; edge[cnt].v v; edge[cnt].flow flow; edge[cnt].next Head[u]; Head[u] cnt;}bool BfsLayer()///使用广搜进行分层{ bool used[MAXN]{0};queueint Q; memset(layer, -1, sizeof(layer)); Q.push(Start); used[Start] true; layer[Start] 0; while(Q.size()) { int s Q.front();Q.pop(); if(s End)return true; for(int iHead[s]; i!-1; iedge[i].next) { int v edge[i].v; if(edge[i].flow !used[v]) { used[v] true; layer[v] layer[s] 1; Q.push(v); } } } return false;}int dfs(int u, int MaxFlow){///MaxFlow 记录的是这条路径上能经过的最大流量 if(u End)return MaxFlow; int uFlow 0;///这个点最多能经过多少流量 for(int iHead[u]; i!-1; iedge[i].next) { int v edge[i].v, flow edge[i].flow; if(layer[v]-1 layer[u] flow) { flow min(MaxFlow-uFlow, flow); flow dfs(v, flow); edge[i].flow - flow; edge[i^1].flow flow; uFlow flow; if(uFlow MaxFlow) break;///已经等于最大流量的时候注意结束 } } return uFlow;}int Dinic()///用dinic算法求最大流{ int MaxFlow 0; while(BfsLayer() true) { MaxFlow dfs(Start, oo); } return MaxFlow;}int main(){ int N, M; while(scanf(%d%d, N, M) ! EOF) { int i, u, v, flow; Start 1, End M, cnt 0; memset(Head, -1, sizeof(Head)); for(i1; iN; i) { scanf(%d%d%d, u, v, flow); AddEdge(u, v, flow); AddEdge(v, u, 0); } printf(%d\n, Dinic()); } return 0;} View Code SAP实现 ************************************************************************************************************************* #includestdio.h#includestring.h#includequeueusing namespace std;const int MAXN 205;const int oo 1e97;struct Edge{int u, v, flow, next;}edge[MAXN*MAXN];int Head[MAXN], cnt;int Layer[MAXN];///分层int start, End;///源点汇点int cur[MAXN], Stack[MAXN],gap[MAXN];int sumV;///节点的总个数void AddEdge(int u, int v, int flow){ edge[cnt].u u; edge[cnt].v v; edge[cnt].flow flow; edge[cnt].next Head[u]; Head[u] cnt;}void BFS(){ memset(Layer, -1, sizeof(Layer)); memset(gap, 0, sizeof(gap)); queueint Q; Q.push(End); Layer[End] 0, gap[0] 1; while(Q.size()) { int u Q.front(); Q.pop(); for(int jHead[u]; j!-1; jedge[j].next) { int v edge[j].v; if(Layer[v] -1) { Layer[v] Layer[u] 1; gap[Layer[v]]; Q.push(v); } } }}int SAP(){ int j, top0, u start, MaxFlow0; BFS(); memcpy(cur, Head, sizeof(Head)); while(Layer[start] sumV) {///源点的层次小于总结点数,汇点是0层 if(u End) { int MinFlow oo, location;///记录下最小流量边的位置出栈时候用 for(j0; jtop; j) { int i Stack[j]; if(MinFlow edge[i].flow) { MinFlow edge[i].flow; location j; } } for(j0; jtop; j) {///所有的边减去路径上的最小流量 int i Stack[j]; edge[i].flow - MinFlow; edge[i^1].flow MinFlow; } MaxFlow MinFlow; top location;///退栈 u edge[Stack[top]].u; } else if(gap[Layer[u]-1] 0) break;///u所在的层下面的层没有了出现了断层也就没有了可行弧 for(jcur[u]; j!-1; jedge[j].next) {///如果u有可行弧就停止 if(Layer[u]Layer[edge[j].v]1 edge[j].flow) break; } if(j ! -1) {///找到了可行弧 cur[u] j;///u点的可行弧是j Stack[top] j;///记录下这条边 u edge[j].v; } else {///没有找到可行弧修改标号 int MinIndex sumV; for(jHead[u]; j!-1; jedge[j].next) {///查找与u相连的最小的层是多少 if(edge[j].flow MinIndex Layer[edge[j].v]) {///记录下这条可行弧,下次可以直接访问这条边 MinIndex Layer[edge[j].v]; cur[u] j; } } gap[Layer[u]] - 1;///u改变层所以u原来所在层的点数减去1 Layer[u] MinIndex 1; gap[Layer[u]] 1; if(u ! start) {///返回上一层 u edge[Stack[--top]].u; } } } return MaxFlow;}int main(){ int N, M; while(scanf(%d%d, N, M) ! EOF) { int i, u, v, flow; sumV M; start 1, End M, cnt 0; memset(Head, -1, sizeof(Head)); for(i1; iN; i) { scanf(%d%d%d, u, v, flow); AddEdge(u, v, flow); AddEdge(v, u, 0); } printf(%d\n, SAP()); } return 0;} View Code转载于:https://www.cnblogs.com/liuxin13/p/4709956.html
