网络流（一）最大流问题EdmondsKarp和最小费用最大流

article/2025/9/28 19:24:42

一、最大流问题

如下图所示，假设需要把一些物品从结点S（称为源点）运送到结点t（称为汇点），可以从其它结点中转。每条边上的权值（左图）表示该条路径最多能运送的物品数，右图边上的权值第一个数表示实际运送的物品数目（flow），第二个数表示最多能运送物品的数目（即容量capacity），也称为题目中的上限。

最大流问题的三个性质：

（1）容量限制：f(u,v)<c(u,v)，即每条边的流量小于容量，对于不存在的边c(u,v)=0；

（2）流量平衡：对于除了s和t结点外的任意结点u, $\sum f(u,v)=0$ ;

（3）斜对称性：f(u,v)=-f(v,u)，把3个物品从u运送到v等同于把3个物品从v运送到u，这样规定f(u,v)和f(v,u)最多只有一个正数（可以均为0）.

问题目标：

从s点流出的净流量（等于t流入的净流量）最大。

二、最大增广路算法

求解最大流问题的算法，从零流（所有边的流量均为0）开始不断增加流量，保持每次增加流量后都满足容量限制，斜对称性和流量平衡三个条件。

如上图所示，根据图（a)中的各边值计算出每条边的容量与流量之差——残余容量，即残量。

例如

s到v2这条边：s->v2=13-8=5; v2->s=0-(-8)=8;

v2到v3这条边：v2->v3=0-(-4)=4; v3->v2=9-4=5;

注意残量网络中的边数可达到原图中边数的两倍。

算法思想：从s到t的任何一条道路都对应原图中的一条增广路（augmenting path)，只要求出该道路中所有残量的最小值d，把对应的所有边上的流量加上d即可，直到d为0不可增加为止停止迭代。

代码如下：

struct Edge
{int from,to,cap,flow;Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d){}
};
struct EdmondsKarp
{int n,m;vector<int> G[maxn];vector<Edge> edges;int a[maxn];int p[maxn];void init(){int i;for(i=0;i<n;i++){G[i].clear();}edges.clear();}void addEdge(int u,int v,int c){edges.push_back(Edge(u,v,c,0));edges.push_back(Edge(v,u,0,0));m=edges.size();G[u].push_back(m-2);G[v].push_back(m-1);}int maxFlow(int s, int t){int flow=0,i,u;for(;;){memset(a,0,sizeof(a));queue<int> q;q.push(s);while(!q.empty()){int x=q.front();q.pop();for(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(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;}
};

采用BFS找增广路，a[]的值为0表示未被访问。

三。最小费用最大流问题

给网络流增加一个因素——费用cost，单位流量所需的cost。如图所示，c和a分别表示容量和费用。有图给出了一个在总流量最大的前提下，总费用最小的流。

在最小费用流中，平行边变得有意义了，可能会有两条边从u到v。由于费用的出现，无法合并这两条弧。先假定图中不存在平行边或反向边，用两个邻接矩阵cap和cost保存各边的容量和费用。为了允许反向增广，规定cap[v][u]=0并且cost[v][u]=-cost[u[[v]。

代码：

struct Edge
{int from,to,cap,flow,cost;Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
};
struct MCMF
{int n,m;vector<int> G[maxn];vector<Edge> edges;int inq[maxn];int d[maxn];int p[maxn];int a[maxn];void init(int n){this->n=n;for(int i=0;i<n;i++){G[i].clear();}edges.clear();}void addEdge(int from,int to,int cap,int cost){edges.push_back(Edge(from,to,cap,0,cost));edges.push_back(Edge(to,from,cap,0,-cost));m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}bool bellmanFord(int s,int t,int& flow,long long &cost){for(int i=0;i<n;i++) d[i]=INF;memset(inq,0,sizeof(inq));d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;queue<int> q;q.push(s);while(!q.empty()){int u=q.front();q.pop();inq[u]=0;for(int i=0;i<G[u].size();i++){Edge& e=edges[G[u][i]];if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){d[e.to]=d[u]+e.cost;p[e.to]=G[u][i];a[e.to]=min(a[u],e.cap-e.flow);if(!inq[e.to]){q.push(e.to);inq[e.to]=1;}}}}if(d[t]==INF) return false;flow+=a[t];cost+=(long long)d[t]*(long long)a[t];for(int u=t;u!=s;u=edges[p[u]].from){edges[p[u]].flow+=a[t];edges[p[u]^1].flow-=a[t];}}int MincostMaxflow(int s,int t,long long &cost){int flow=0;cost=0;while(bellmanFord(s,t,flow,cost));return flow;}
};

没有再采用BFS，而是BellmanFord算法寻找增广路。只要初始流是该流量下的最小费用可行流，每次增广后的新流都是新流量下的最小费用流。