EdmondKarp算法：
Map[MAXN][MAXN],pre[MAXN]; //Pre[]前驱数组int N,NP,NC,M;bool EkBFS(int start,int end) //宽度优先搜索寻找增广路{(vis,false,sizeof(vis));memset(pre,-1,sizeof(pre)); //初始化Q.push(start);vis[start] = true;while( !Q.empty() ){int u = Q.front();;Q.pop();for(int i = 0; i <= N+1; ++i){if(Map[u][i] && !vis[i]) //当边容量为非零，且增广路点未标记{vis[i] = true;pre[i] = u; //记录前驱Q.push(i); //入队}}}return false;}int EkMaxFlow(int start,int end) //网络流的源点和汇点{int v,Ans = 0,MinN;//初始化最大流Ans = 0while(EkBFS(start,end)) //当增广成功{MinN = 0xffffff0;v = end;while( pre[v] != -1){MinN = min(MinN,Map[pre[v]][v]);v = pre[v];} //寻找”瓶颈”边，，并且标记容量Ans += MinN; //累加进最大流v = end;while( pre[v] != -1){Map[pre[v]][v] -= MinN;Map[v][pre[v]] += MinN;v = pre[v];} //修改路径上的边容量}return Ans;} //初始化 memset(Map,0,sizeof(Map)); scanf(“%d%d”,&N,&M); for(int i = 0; i < M; ++i) {scanf(“%d%d%d”,&u,&v,&w);Map[u][v] += w; }printf(“Case %d: %d\n”,++kase, EkMaxFlow(1,N));
SAP算法：
MAXM = MAXN*4;const int INF = 0xffffff0;struct EdgeNode{int to;int next;int w;}Edges[MAXM];int Head[MAXN],id;//链式前向星void AddEdges(int u,int v,int w){Edges[id].to = v;Edges[id].w = w;Edges[id].next = Head[u];Head[u] = id++;Edges[id].to = u;Edges[id].w = 0;Edges[id].next = Head[v];Head[v] = id++;}int Numh[MAXN],h[MAXN],curedges[MAXN],pre[MAXN];BFS(int end,int N) //BFS求出每个点的距离标号值{memset(Numh,0,sizeof(Numh));for(int i = 1; i <= N; ++i)Numh[h[i]=N]++;h[end] = 0;Numh[N]–;Numh[0]++;queue<int> Q;Q.push(end);while(!Q.empty()){int v = Q.front();Q.pop();int i = Head[v];while(i != -1){int u = Edges[i].to;if(h[u] < N){i = Edges[i].next;continue;}h[u] = h[v] + 1;Numh[N]–;Numh[h[u]]++;Q.push(u);i = Edges[i].next;}}}int SAPMaxFlow(int start,int end,int N){int CurFlow,FlowAns = 0,temp,neck; //FlowAns:最大流，初始化为0memset(h,0,sizeof(h));memset(pre,-1,sizeof(pre));for(int i = 1; i <= N; ++i)curedges[i] = Head[i];//初始化当前弧为第一条邻接边//Numh[0] = N;BFS(end,N);int u = start;while(h[start] < N)//当h[start] >= N时，网络中肯定出现了GAP{if(u == end){CurFlow = INF;for(int i = start; i != end; i = Edges[curedges[i]].to){if(CurFlow > Edges[curedges[i]].w){neck = i;CurFlow = Edges[curedges[i]].w;}} //增广成功，寻找”瓶颈”边for(int i = start; i != end; i = Edges[curedges[i]].to){temp = curedges[i];Edges[temp].w -= CurFlow;Edges[temp^1].w += CurFlow;} //修改路径上的边容量FlowAns += CurFlow;u = neck; //下一次增广从瓶颈边开始}int i;for(i = curedges[u]; i != -1; i = Edges[i].next)if(Edges[i].w && h[u] == h[Edges[i].to]+1)break; //寻找可行弧if(i != -1)//GAP优化{curedges[u] = i;pre[Edges[i].to] = u;u = Edges[i].to;}else{if(0 == –Numh[h[u]])break;curedges[u] = Head[u];for(temp = N,i = Head[u]; i != -1; i = Edges[i].next)if(Edges[i].w)temp = min(temp,h[Edges[i].to]);h[u] = temp + 1;++Numh[h[u]];if(u != start)//重新标号并从当前点前驱重新增广u = pre[u];}}return FlowAns;}//初始化memset(Head,-1,sizeof(Head)); id = 0; for(int i = 0; i < N; ++i) {scanf(“%d%d%d”,&u,&v,&w);AddEdges(u,v,w); } printf(“%d\n”,SAP(1,M,M));
回避现实的人，未来将更不理想。
