代码介绍：
文件数据格式：点的数量，边的数量，源点序号，汇点序号
每条边：起点，终点，容量
从文件中读取数据，构建网络流图，使用dinic算法求解最大流，采用数组邻接表存储数据。
求最大流过程：不断找一条源点到汇点的路径，若有，找出增广路径上每一段权值的最小值，然后构建残余网络。再在残余网络上寻找新的路径，再依据路径的最小值，构建新的残余网络，再寻找新的路径...直至某个残余网络找不到从源点到汇点的路径为止，最大流即为每次最小值之和。
Dinic算法：
先使用宽度优先搜索，根据源点到每个点的最短距离(边数)不同，对每个点进行分层，只要进行到计算出汇点的层次数，即为分层成功。
之后利用深度优先搜索从前一层向后一层反复寻找增广路径，寻找的增广路径要求满足所有的点分别属于不同的层，且点应满足deppv=deppv-1+1。DFS过程中，进行到了汇点，则说明找到了一条增广路径，此时对总流量进行增加，并消减增广路径各边的容量，并添加反向边，即进行增广。找到一条增广路径后，回溯继续寻找下一个增广路径。
DFS结束后，对残余网络再次进行分层，当分层操作无法算出汇点的层次是，即求得最大流。
头文件：
1 #include <queue> 2 #include <fstream> 3 #include <iostream> 4 #include <string> 5 using namespace std; 6 const int inf = 0x3f3f3f3f; 7 const int worker_number = 5000; 8 const int task_number = 5000; 9 10 struct Edge 11 { 12 int to; 13 int next; 14 int cap; 15 }; 16 17 class Graph 18 { 19 private: 20 int src;//源点 21 int dst;//汇点 22 int edge_num;//边数 23 int note_num;//点数 24 int num; 25 int max_flow; 26 int head[worker_number + task_number + 3]; 27 int cur[worker_number + task_number + 3]; 28 int level[worker_number + task_number]; 29 Edge edges[worker_number + task_number]; 30 queue<int> Q; 31 void add_edge(int from,int to,int dis); 32 bool bfs(int begin, int end); 33 int dfs(int now,int flow); 34 35 36 public: 37 Graph(int n = 0, int m = 0, int s = 0, int d = 0); 38 void read(string file_name);//从文件中读取数据 39 int Dinic(); 40 }; 41 42 Graph::Graph(int n,int m,int s,int d) 43 { 44 this->note_num = n; 45 this->edge_num = m; 46 this->src = s; 47 this->dst = d; 48 this->max_flow = 0; 49 this->num = -1; 50 51 memset(this->head, -1, sizeof(this->head)); 52 memset(this->cur, -1, sizeof(this->cur)); 53 memset(this->level, -1, sizeof(this->level)); 54 } 55 56 void Graph::add_edge(int from,int to,int dis) 57 { 58 this->edges[++this->num].next = this->head[from]; 59 this->edges[this->num].to = to; 60 this->edges[this->num].cap = dis; 61 this->head[from] = this->num; 62 } 63 64 void Graph::read(string file_name) 65 { 66 ifstream fin(file_name); 67 int x, y, z; 68 69 if (fin.good()) 70 { 71 //n结点数，m边数，s源点，d汇点 72 fin >> this->note_num >> this->edge_num >> this->src >> this->dst; 73 this->num = -1; 74 75 for (int i = 0;i < this->edge_num;i++) 76 { 77 //边：起点，终点，容量 78 fin >> x >> y >> z; 79 80 this->add_edge(x, y, z);//添加边 81 this->add_edge(y, x, 0);//添加反向边 82 } 83 } 84 else 85 { 86 cout << "文件打开失败！" << endl; 87 exit(0); 88 } 89 90 fin.close(); 91 } 92 93 //利用bfs进行分层 94 bool Graph::bfs(int begin, int end) 95 { 96 memset(this->level, -1, sizeof(this->level));//更新层次，对残余网络进行分层 97 int now;//当前点 98 99 while (!this->Q.empty())this->Q.pop(); 100 this->level[begin] = 0;//起点深度为0 101 this->Q.push(begin); 102 103 while (!this->Q.empty()) 104 { 105 now = this->Q.front(); 106 this->Q.pop(); 107 108 for (int i = this->head[now];i != -1;i = this->edges[i].next) 109 { 110 //如果该点没有被标记层次并且该边的流量不为零 111 if (this->level[this->edges[i].to] == -1 && this->edges[i].cap) 112 { 113 this->level[this->edges[i].to] = this->level[now] + 1; 114 this->Q.push(this->edges[i].to); 115 } 116 } 117 } 118 119 return this->level[this->dst] != -1;//若没有到达汇点，则返回false 120 } 121 122 //flow为源点到now的路径中的最小边权 123 int Graph::dfs(int now, int flow) 124 { 125 if (now == this->dst)return flow;//如果当前点为汇点，则返回flow 126 127 int detla = flow, d, f; 128 for (int i = this->cur[now];i != -1;i = this->edges[i].next) 129 { 130 //寻找路径时，点要属于不同的层次并且边为通 131 if (this->level[this->edges[i].to] == (this->level[now] + 1) && (this->edges[i].cap > 0)) 132 { 133 //向下递归，求后续结点的最大流量，即最小边权 134 this->cur[now] = this->edges[i].next; 135 d = (detla < this->edges[i].cap) ? detla : this->edges[i].cap; 136 f = this->dfs(this->edges[i].to, d); 137 138 this->edges[i].cap -= f; 139 //处理反向边，存边时从0开始，边和其反向边相邻 140 this->edges[i ^ 1].cap += f; 141 detla -= f;//更新本节点的残余量 142 //若本节点的残余量消耗完，则返回 143 if (detla == 0)break; 144 } 145 } 146 147 return flow - detla;//返回该点已经被允许流过的流量 148 } 149 150 int Graph::Dinic() 151 { 152 while (this->bfs(this->src, this->dst)) 153 { 154 for (int i = 1;i <= this->note_num;i++)this->cur[i] = this->head[i]; 155 this->max_flow += this->dfs(this->src, inf); 156 } 157 158 return this->max_flow; 159 }
源文件：
1 #include "标头.h" 2 3 int main() 4 { 5 Graph G; 6 string file_name; 7 8 cout << "请输入存储数据的文件" << endl; 9 cin >> file_name; 10 11 G.read(file_name); 12 cout << "最大流：" << G.Dinic() << endl; 13 14 return 0; 15 }