网络流初步

问题：最大流问题

假设：把一些物品从结点s（源点），运送到t（汇点），可以从其他结点中转。

相关定义：

1.容量：对于一条边(u,v)，它的物品上限成为容量，记为c(u,v)

2.流量：实际运送的物品成为流量，记为f(u,v)

目标：最大化从s点流出的净流量，即最大化

容量c与流量f满足3个性质：

1.容量限制：对G中的每条边(vi,vj)，有0≤fij≤cij；即每条边上的流量非负而且最大也只能达到容量的限制。 2.流量平衡：对中间点（除了结点是s，t），有   3.斜对称性：

增广路算法：

残量网络：由计算出的流量和容量之差的边作出的图

基本思想：求出增广路中所有残量的最小值d，再把对应的所有边上的流量增加d即可。

#include<iostream> #include<queue> #include<cstring> #include<cstdio> using namespace std; const int MAXN = 20; //设定权值最大值为20 const int INF = (1 << 30); //定义字符常量 inf 并赋值一个很大的值。inf=1073741824 //1 << 30 表示 1*2^30 struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {} }; struct EdmondsKarp { int n, m; vector < Edge > edges; vector < int > G[MAXN]; int a[MAXN]; int p[MAXN]; void init(int n) { for (int i = 0; i < n; ++i) { G[i].clear(); } edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); //反向弧 m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } int Maxflow(int s, int t) { int flow = 0; for (;;) { memset(a, 0, sizeof a); queue < int > Q; Q.push(s); a[s] = INF;//初始源点有无限个物品 while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); ++i) { Edge &e = edges[G[x][i]]; if (!a[e.to] && e.cap > e.flow) { // 查找任意边流动物品 p[e.to] = G[x][i]; a[e.to] = min(a[x], e.cap - e.flow); Q.push(e.to); } } if (a[t]) { //如果有增广路，退出 break; } } if (!a[t]) { //没有增广路，现在的结果即为最大流 break; } for (int u = t; u != s; u = edges[p[u]].from) { // 反向修改流量 edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } flow += a[t];//增加总流量 } return flow; } } ek;

最小割最大流定理：

最小割：把所有顶点分成两个集合S和T=V-S，其中源点在集合S中，汇点在集合T中。

在增广路算法结束时，f是s-t最大流，(S,T)是s-t的最小割