首页 > 代码库 > graph | Max flow
graph | Max flow
最大流算法，解决的是从一个起点到一个终点，通过任何条路径能够得到的最大流量。
有个Edmond-Karp算法：
1. BFS找到一条增广路径；算出这条路径的最小流量（所有边的最小值）increase；
2. 然后更新路径上的权重（流量），正向边加上increase，反向边减去increase;
3. 重复1，直到没有增广路径；
至于为什么要用反向边，这里讲得挺清楚；
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <limits.h> 5 #include <vector> 6 using namespace std; 7 8 class Maxflow { 9 public:10 11 Maxflow() {}12 ~Maxflow() {13 if (pre) delete[] pre;14 if (flow) delete[] flow;15 if (weight) {16 for (int i = 0; i < vertices; ++i) {17 delete[] weight[i];18 }19 delete[] weight;20 }21 }22 void readGraph(string filename) {23 freopen(filename.c_str(), "r", stdin);24 int edges;25 scanf("%d %d", &vertices, &edges);26 pre = new int[vertices];27 flow = new int[vertices];28 memset(flow, 0, vertices * sizeof(int));29 weight = new int*[vertices];30 for (int i = 0; i < vertices; ++i) {31 weight[i] = new int[vertices];32 memset(weight[i], 0, vertices * sizeof(int));33 }34 35 for (int i = 0; i < edges; ++i) {36 int v1, v2, w;37 scanf("%d %d %d", &v1, &v2, &w);38 weight[v1 - 1][v2 - 1] = w;39 }40 }41 42 int maxFlow() {43 int start = 0, end = vertices - 1;44 int max = 0;45 int increase = 0;46 while ((increase = bfs(start, end)) != 0) {47 int p = end;48 while (p != start) {49 int b = pre[p];50 weight[b][p] -= increase;51 weight[p][b] += increase;52 p = b;53 }54 max += increase;55 }56 return max;57 }58 private:59 int bfs(int start, int end) {60 memset(pre, -1, vertices * sizeof(int));61 vector<vector<int> > layers(2);62 int cur = 0, next = 1;63 layers[cur].push_back(start);64 flow[start] = INT_MAX;65 66 while (!layers[cur].empty()) {67 layers[next].clear();68 for (int i = 0; i < layers[cur].size(); ++i) {69 int v1 = layers[cur][i];70 for (int v2 = 0; v2 < vertices; ++v2) {71 if (weight[v1][v2] <= 0 || pre[v2] != -1) continue;72 pre[v2] = v1;73 layers[next].push_back(v2);74 flow[v2] = min(flow[v1], weight[v1][v2]);75 if (v2 == end) return flow[v2];76 }77 }78 79 cur = !cur;80 next = !next;81 }82 return 0;83 }84 int* pre;85 int** weight;86 int* flow;87 int vertices;88 };89 90 int main() {91 Maxflow maxflow;92 maxflow.readGraph("input.txt");93 cout<< maxflow.maxFlow() << endl;94 return 0;95 }
sample input:
1 4 52 1 2 403 1 4 204 2 4 205 2 3 306 3 4 10
graph | Max flow
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。