最大流一般可以解决像货运这种问题,例如POJ1273,一共n个池塘m条边,给出每条边能通过的最大水流量,给出一个起点和一个汇点,问起点流出的最大水流量是多少。基本算法是Edmonds-Karp算法:循环增加流的值,每次通过BFS寻找一个增长路径(从起点到汇点的简单路径),每次将路径中最小的残余边量(容量减当前流量)加入流量,同时更新残余边和它的反向边,直到图中没有增长路径,此时的流即为最大流。
增长路径的查询可以用BFS实现,这里比较难理解的是反向边的处理,反向边主要是用来让流自我调整的,详细的可以参考下面这博客:
参考博客:点击打开链接
POJ1273:最大流的模板题:
| 15965695 | Seasonal | 1273 | Accepted | 740K | 0MS | C++ | 944B | 2016-08-16 14:50:14 |
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int s, t,n,m;
int flow[250][250], map[250][250], pre[250], a[250];void FordFulkerson()
{int i, u, v;int sum = 0;s = 1; t = n;memset(flow, 0, sizeof(flow));queue<int> que;while (1){memset(a, 0, sizeof(a));a[s] = 0xffffff;que.push(s);while (!que.empty()){u = que.front();que.pop();for (v = 1; v <= n; v++){if (!a[v] && flow[u][v] < map[u][v]){pre[v] = u;//pre存储前驱que.push(v);a[v] = min(a[u], map[u][v] - flow[u][v]);//s-v路径上的最小残量}}}if (a[t] == 0)//没有增广路径,达到最大流break;sum += a[t];for (i = t; i != s; i = pre[i]){flow[pre[i]][i] += a[t];//更新正向边的流量flow[i][pre[i]] -= a[t];//更新反向边的流量}}cout << sum << endl;
}int main()
{int x,y,w;while (cin >> m >> n){memset(map, 0, sizeof(map));for (int i = 0; i < m; i++){cin >> x >> y;cin >> w;map[x][y] += w;//可能有重复边}FordFulkerson();}return 0;
}