最大流问题

偏执的太偏执、 2021-11-10 17:36 357阅读 0赞

# 定义 #

有m条管道，n个节点，1为水源(源点)，n为终点(汇点)，每条管道有水流量上限，问如何分配每条水管的流量才能使终点处接受到的水流量最大。

最小割最大流定理：是指在一个网络流中，能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。

--------------------

## 算法&模板 ##

#### EK（最短增广路算法） ####

流：从源点开始，在汇点结束的路径，有大小（即流量）。  
容量网络：初始输入的各边的容量。  
流量网络：计算中已有的水流量，即对汇点做出贡献的流量。  
残量网络：容量网络-流量网络（开始就是容量网络）。  
增广路：在残量网络上建立的新的合法的可以对汇点做出贡献的一条流。

EK算法：寻找最短的新的增广路，累积贡献，直至找不到为止。  
实现：每次通过bfs寻找增广路，每次加入一条新的边，同时建立一条反向边(便于让后面的流合理分配地占据先前的流的边)

**邻接矩阵版本（更快）：**

#include <cstdio> #include <iostream> #include <queue> using namespace std; typedef long long ll; const int maxn=205; const ll INF=1e17; ll cap[maxn][maxn],flow[maxn][maxn]; ll minr[maxn];//从起到到该店地最小残量 ll fa[maxn];//流上靠近起点的父节点 ll n,m,maxf=0; ll EK(){ maxf=0; ll s=1,t=m; while(1){ fill(minr,minr+m+5,0); minr[s]=INF; queue<ll>q; q.push(s); while(!q.empty() ){ ll u=q.front(); q.pop(); for(ll v=1;v<=m;v++){ if(!minr[v] && cap[u][v]>flow[u][v]){//minr[]作vis标记 fa[v]=u; q.push(v); minr[v]=min(minr[u],cap[u][v]-flow[u][v]); } } if(minr[t]) break; } if(!minr[t]) break; for(ll v=t;v!=s;v=fa[v]){ flow[fa[v]][v]+=minr[t];//正向流量增加 flow[v][fa[v]]-=minr[t];//反向流量减少 } maxf+=minr[t]; } } int main(){ scanf("%lld%lld",&n,&m); ll x,y,c; for(int i=1;i<=n;i++){ scanf("%lld%lld%lld",&x,&y,&c); cap[x][y]+=c;//出现平行边时容量相加 } EK(); printf("%lld\n",maxf); }

--------------------

**邻接表版本（点过多时用邻接表避免MLE）:**

#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; typedef long long ll; const int maxn=1e4+5; const ll INF=1e17; struct edge{ ll from,to,cap,flow; edge(ll f=0,ll t=0,ll c=0,ll fl=0):from(f),to(t),cap(c),flow(fl){} }; vector<edge>ed; vector<ll>G[maxn];//存点i连接的边的编号 ll minr[maxn];//最小残余流 ll fa[maxn];//存靠近源的边的编号 ll cnt,n,m,maxf,s,t; void addedge(ll from,ll to,ll cap){ ed.push_back(edge(from,to,cap,0)); ed.push_back(edge(to,from,0,0));//反向边容量为0 cnt=ed.size(); G[from].push_back(cnt-2); G[to].push_back(cnt-1);//反向边 } void EK(){ maxf=0; while(1){ fill(minr,minr+n+5,0); minr[s]=INF; queue<ll>q; q.push(s); while(!q.empty()){ ll u=q.front(); q.pop(); for(int i=0;i<G[u].size();i++){ edge &e=ed[G[u][i]]; if(!minr[e.to]&&e.cap>e.flow){ fa[e.to]=G[u][i]; q.push(e.to); minr[e.to]=min(minr[u],e.cap-e.flow); } } if(minr[t])break;//一旦找到一个增广路立即跳出(缩时关键) } if(!minr[t]) break; for(ll u=t;u!=s;u=ed[fa[u]].from){ ed[fa[u]].flow+=minr[t]; ed[fa[u]^1].flow-=minr[t]; } maxf+=minr[t]; } } void init(){ ed.clear(); for(int i=0;i<=n;i++) G[i].clear(); } int main(){ scanf("%lld%lld%lld%lld",&n,&m,&s,&t); init(); ll x,y,w; for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&x,&y,&w); addedge(x,y,w); } EK(); printf("%d\n",maxf); }

--------------------

## 例题 ##

##### Path [http://acm.hdu.edu.cn/showproblem.php?pid=6582][http_acm.hdu.edu.cn_showproblem.php_pid_6582] #####

给定一个边权有向图，问用最小的代价(边权和最小)切断一些边，使得起点到终点的最短路变长。

解法：  
将所有最短路合并成新的图，该图的最小割(最大流)就是解。  
最短路建图的方法：枚举每条边，若该边到起点与终点的距离和+该边边权=最短路，该边就在最短路上。

#include <cstring> #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long ll; const ll maxn=1e4+5; const ll INF=1e17; ll n,m; struct qnode{ ll v; ll c;//距原点距离 qnode(ll _v=0,ll _c=0):v(_v),c(_c){} bool operator <(const qnode &r)const{ return c>r.c;//大于小于反转<=>将距离更短的点放上面 } }; struct Edge{ ll v,cost;//v表示相连的顶点 Edge(ll _v=0,ll _cost=0):v(_v),cost(_cost){} }; vector<Edge>E[maxn]; bool vis[maxn]; ll dis1[maxn],dis2[maxn]; ll a[maxn],b[maxn],w[maxn]; void dijkstra(ll start,ll dis[]){ fill(dis,dis+n+5,INF); priority_queue<qnode>q;//存点 while(!q.empty() ) q.pop(); dis[start]=0; q.push(qnode(start,0)); qnode tmp; while(!q.empty() ){ tmp=q.top(); q.pop(); ll u=tmp.v ; if(vis[u])continue ; vis[u]=1;//将该点加入集合 for(ll i=0;i<E[u].size() ;i++){//遍历和u相连的边 ll v=E[u][i].v;//v是和u相连的点 ll cost=E[u][i].cost; if(!vis[v]&&dis[v]>dis[u]+cost){ dis[v]=dis[u]+cost; q.push(qnode(v,dis[v]));//用新的数据(更小的c)代替旧数据 } } } } void addedge1(ll u,ll v,ll w){ E[u].push_back(Edge(v,w)); } struct edge{ ll from,to,cap,flow; edge(ll f=0,ll t=0,ll c=0,ll fl=0):from(f),to(t),cap(c),flow(fl){} }; vector<edge>ed; vector<ll>G[maxn];//存点i连接的边的编号 ll minr[maxn];//最小残余流 ll fa[maxn];//存靠近源的边的编号 ll cnt,maxf,s,t; void addedge2(ll from,ll to,ll cap){ ed.push_back(edge(from,to,cap,0)); ed.push_back(edge(to,from,0,0));//反向边容量为0 cnt=ed.size(); G[from].push_back(cnt-2); G[to].push_back(cnt-1);//反向边 } void EK(){ maxf=0; while(1){ fill(minr,minr+n+5,0); minr[s]=INF; queue<ll>q; q.push(s); while(!q.empty()){ ll u=q.front(); q.pop(); for(int i=0;i<G[u].size();i++){ edge &e=ed[G[u][i]]; if(!minr[e.to]&&e.cap>e.flow){ fa[e.to]=G[u][i]; q.push(e.to); minr[e.to]=min(minr[u],e.cap-e.flow); } } if(minr[t])break;//一旦找到一个增广路立即跳出(缩时关键) } if(!minr[t]) break; for(ll u=t;u!=s;u=ed[fa[u]].from){ ed[fa[u]].flow+=minr[t]; ed[fa[u]^1].flow-=minr[t]; } maxf+=minr[t]; } } void init(){ for(ll i=0;i<=n;i++) E[i].clear(); fill(vis,vis+n+5,0); } void init2(){ ed.clear(); for(int i=0;i<=n;i++) G[i].clear(); } int main(){ ll T; scanf("%lld",&T); while(T--){ init(); scanf("%lld%lld",&n,&m); for(ll i=1;i<=m;i++){ scanf("%lld%lld%lld",&a[i],&b[i],&w[i]); addedge1(a[i],b[i],w[i]); } dijkstra(1,dis1); init(); for(ll i=1;i<=m;i++){ addedge1(b[i],a[i],w[i]); } dijkstra(n,dis2); ll mosts=dis1[n]; if(mosts==1e17){ printf("0\n"); continue; } init2(); for(ll i=1;i<=m;i++){ if(dis1[a[i]]+dis2[b[i]]+w[i]==mosts){ addedge2(a[i],b[i],w[i]); } } s=1;t=n; EK(); printf("%lld\n",maxf); } return 0; }

转载于:https://www.cnblogs.com/ucprer/p/11255611.html

[http_acm.hdu.edu.cn_showproblem.php_pid_6582]: http://acm.hdu.edu.cn/showproblem.php?pid=6582