再谈网络流

本文主要是介绍再谈网络流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里我已经讨论过网络流最大流基本算法，但是我们可以对这个算法进行时间上的优化。其中效果比较好的当属“最短增广路算法”，即每次都沿着最短增广路（即边数最少的增广路）进行增广。下面要介绍的算法均使用如下数据结构来表示一条弧。

struct Edge {int from, to,cap,flow;
};

这代表一条从from到to的容量为cap，流量为flow的弧。当且仅当flow<cap的时候，该弧存在于残量网络中。当cap=0的时候，意味着此边事反向弧，此时flow<=0。下面是插入弧的过程。注意，原图中的一条弧对应两个Edge结构体，一个是这条弧本身，另一个是它的反向弧。根据插入顺序不难看出，edge[0]和edge[1]互为反向弧。一般地，edge[x]与edge[x^1]互为反向弧。

void AddEdge (int from, int to, int cap){edges.push_back((Edge){from,to,cap,0});edges.push_back((Edge){from,to,0,0});m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1);
}

这个数据结构兼顾了效率，代码清晰度和调试难度，它的最大的好处就是同时适用于稠密图和稀疏图，而且支持重边。我们很快就会看到，重边在最小费用流里是不能避免的。

Dinic算法。我们要介绍的第一种算法称为Dinic算法，从宏观上讲，该算法就是不停地用BFS构造层次图，然后用阻塞流来增广。“层次图”和阻塞流“是Dinic算法的关键词。什么叫层次图？假设在残量网络中，起点到结点u的距离为dist(u)，我们把dist(u)看成结点u的”层次“。只保留每个点出发到下一层次的弧，得到的图就是层次图。（这里看不懂概念并不是很重要，可以通过下面的源代码理清程序思路）

struct Edge {int from, to, cap, flow;
}void AddEdge (int from, int to, int cap){edges.push_back((Edge){from,to,cap,0});edges.push_back((Edge){from,to,0,0});m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1);
}int n,m,s,t; //结点数，边数（包括反向弧），源点编号，汇点编号
vector<Edge> edges; //边表 edge[e]和edge[e^1]互为反向弧
vector<int> G[maxn]; //邻接表，G[i][j]表示点i的第j条边在e数组中得序号
bool vis[maxn];   //BFS中使用
int d[maxn]  //从起点到i的距离
int cur[maxn]  //当前弧下表 （后面继续说明）bool BFS (){memset(vis,0,sizeof(vis));queue<int> q;q.push(s);d[s] = 0;vis[s] = 1;while(!q.empty()){int u = q.front(), q.pop();for(int i = 0; i < G[u].size(); i++){Edge& e = edges[G[u][i]];if(!vis[e.to] && e.cap > e.flow){vis[e.to] = 1;d[e.to] = d[u] + 1;q.push(e.to);}}}return vis[t];
}int DFS (int x, int a) //DFS过程除了当前结点x外，还需要传入一个表示目前为止所有弧的最小残量的a，当x为汇点，或者a=0时终止DFS过程，否则多路增广。这里还有一个重要的优化：保存每个结点x正在考虑的弧cur[x]，以避免重复计算
{if(x==t || a==0) return a;int f, flow = 0;for(int& i = cur[x]; i < G[x].size(); i++){Edge& e = edges[G[x][i]];if(d[x]+1==d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow))) > 0){e.flow += f;edges[G[x][i]^1] -= f;flow += f;a -= f;if(a==0) brea;}}return flow;
}
//最后主过程，不停的用BFS构造分层网络，然后用DFS沿着阻塞流增广。
int MaxFlow (){int flow = 0;while(BFS()){memset(cur,0,sizeof(cur));flow += DFS(s,INF);}return flow;
}

这篇关于再谈网络流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---