本文主要是介绍poj1273 最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用的是EdmondsKarp
程序可以再优化的，懒得优化了
EdmondsKarp
#include <iostream>
#include<stdio.h>
#include <queue>
#include <limits>
#include <cstring>using namespace std;
const int maxNode = 202;
int N = 201;//edge
int M = 201;//node
const int maxInt = numeric_limits<int>::max();int g[maxNode][maxNode];
int f[maxNode][maxNode];
int residual[maxNode][maxNode];
int pre[maxNode];bool BFS()
{queue<int> q;q.push(1);memset(pre,0,sizeof(int)*(M+1));int used[maxNode];memset(used,0,sizeof(int)*(M+1));used[1] = 1;while (!q.empty()){int curr = q.front();q.pop();for (int i=1;i<=M;++i){if(residual[curr][i]>0 && !used[i]){pre[i] = curr;if(i==M)return true;q.push(i);used[i] = 1;}}}return false;
}void EdmondsKarp()
{while (BFS()){int minF = maxInt;int curr = M;int beg=0,end = 0;while (curr!=1){int preNode = pre[curr];if(minF > residual[preNode][curr]){minF = residual[preNode][curr];beg = preNode;end = curr;}curr = preNode;}curr = M;while (curr != 1){int preNode = pre[curr];f[preNode][curr] +=minF;residual[preNode][curr] -=minF;residual[curr][preNode] = f[preNode][curr];curr = preNode;}}int sum=0;for (int i=1;i<M;++i){sum +=f[i][M];}cout<< sum<<endl;
}int main()
{while(scanf("%d%d",&N,&M)!=EOF){for (int i=1;i<=M;++i){memset(g[i],0,sizeof(int)*(M+1));memset(f[i],0,sizeof(int)*(M+1));memset(residual[i],0,sizeof(int)*(M+1));}for (int i=0;i<N;++i){int start,end,capacity;scanf("%d%d%d",&start,&end,&capacity);g[start][end] += capacity;//这个地方太坑爹了，不是最大的容量吗，为毛要加呢residual[start][end] += capacity;}/*for (int i=1;i<=M;++i){for(int j=1;j<=M;++j)cout<<g[i][j]<<" ";cout<<endl;}*/EdmondsKarp();}return 0;
}
下面是别人优化的比较好的
#include<iostream>#include<cstring>
#include<queue>
using namespace std;
#define inf INT_MAX
int n,m,a[205][205],pre[205];
int bfs()
{queue<int>Q;Q.push(1);pre[1]=0;memset(pre,-1,sizeof(pre));int t,i;while(!Q.empty()){t=Q.front();Q.pop();for(i=2;i<=n;i++)if(pre[i]==-1&&a[t][i]>0){pre[i]=t;Q.push(i);if(i==n) return 1;}}return -1;
}
int maxflow()
{int res=0,ans,t;while(bfs()==1){t=n;ans=inf;while(t!=1){if(a[pre[t]][t]<ans) ans=a[pre[t]][t];t=pre[t];} res=res+ans;t=n;while(t!=1){a[pre[t]][t]-=ans;a[t][pre[t]]+=ans;t=pre[t];}}return res;
}
int main()
{while(scanf("%d%d",&m,&n)!=EOF){int i,j;memset(a,0,sizeof(a));for(i=0;i<m;i++){int b,c,d;scanf("%d%d%d",&b,&c,&d);a[b][c]+=d;}printf("%d\n",maxflow());}
}最大流效率更高的算法为：
Push-Relabel算法
Relabel-to-Front算法（http://cuitianyi.com/blog/%E6%B1%82%E6%9C%80%E5%A4%A7%E6%B5%81%E7%9A%84relabel-to-front%E7%AE%97%E6%B3%95/）
Preflow-Push算法
Dinic算法（可以参考国家集训队 2007 王欣上《浅谈基于分层思想的网络流算法》）
这篇关于poj1273 最大流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
