带上下界的网络流的学习笔记啦~
注意：代码还在路上。
无源汇上下界可行流
模型
给定一个网络，求一个流，满足每条边的流量都 \(min⩽flow⩽max\) ，并且每个点都满足 总流入量=总流出量（流量守恒） ，没有源汇。
思路
核心是将一个不满足流量守恒的初始流调整成满足流量守恒的流
初始流，不一定满足流量守恒，每条边的流量都是这条边的流量下界
附加流，不一定满足流量守恒，但是和初始流的叠加流满足流量守恒
新增虚拟源点汇点\(s,t\)
设\(d[i]=\)流入量-流出量
- \(d[i]>0\) ，\(s\)向\(i\)连流量为\(d[i]\)的边
- \(d[i]<0\)，\(i\)向\(t\)连流量为\(-d[i]\)的边
每条边的流量变为\(up-down\)，就是上界减下界
有可行流的必要条件是\(s\)的出边的流量总和等于\(t\)的入边的流量总和
存在可行流的条件\(s\)到\(t\)的最大流\(=\sum_{d[i]>0} d[i]\)
最后，每条边的实际流量就是初始流+附加流
Code
咕咕咕
有源汇上下界可行流
模型
满足源点流出量\(=\)汇点流入量，其它节点流量守恒，每条边都满足上下界限制
思路
建一条从\(t\)到\(s\)的边上界为\(inf\)，下界为\(0\)，这样就可以转化成无源汇的模型
然后最后整个网络的流量就是边\(t \rightarrow s\)的流量
Code
咕咕咕
有源汇上下界最大流
模型
有源汇的可行流的情况下满足总流量最大
思路
最大流\(=\)可行流流量\(+\)新增广的\(s\)到\(t\)的最大流
在求完可行流之后，在对原图的残余网络求一次最大流
因为是在更改附加流，对原来的流量上界不会造成影响
Code
咕咕咕
有源汇上下界最小流
模型
有源汇的可行流的情况下满足总流量最小
思路
最大流\(=\)可行流流量\(-\)新增广的\(t\)到\(s\)的最小流
相当于是在跑反向边，跑的过程中是不会改变流量守恒的
而且是在更改附加流，对原来的流量下界也不造成影响
Code
// lp 4843 清理雪道#include#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define reg registerinline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}const int MN=105,inf=0x3f3f3f3f;int step[MN],q[MN],top;struct edge{int to,w,nex;}e[MN*MN<<1];int en=1,cur[MN],hr[MN];inline void ins(int x,int y,int w){ e[++en]=(edge){y,w,hr[x]};hr[x]=en; e[++en]=(edge){x,0,hr[y]};hr[y]=en;}bool bfs(int S,int T){ memset(step,0,sizeof step); reg int i,j; for(step[q[i=top=1]=S]=1;i<=top;++i) for(j=hr[q[i]];j;j=e[j].nex) if(e[j].w&&!step[e[j].to]) step[q[++top]=e[j].to]=step[q[i]]+1; return step[T];}int dfs(int x,int T,int f){ if(x==T) return f; int used=0; for(int &i=cur[x];i;i=e[i].nex) if(e[i].w&&step[e[i].to]==step[x]+1) { int tmp=dfs(e[i].to,T,min(f-used,e[i].w)); e[i].w-=tmp,e[i^1].w+=tmp;used+=tmp; if(f==used) return f; } return step[x]=-1,used;}int dinic(int S,int T){ int maxflow=0; while(bfs(S,T)) { memcpy(cur,hr,sizeof cur); maxflow+=dfs(S,T,inf); } return maxflow;}int ss,tt,s,t,n,d[MN],ans;int main(){ n=read(); int s=n+1,t=n+2,ss=n+3,tt=n+4; reg int i,j,k; for(i=1;i<=n;++i) { j=read(); while(j--) k=read(),ins(i,k,inf),--d[i],++d[k]; } for(i=1;i<=n;++i) ins(s,i,inf),ins(i,t,inf); ins(t,s,inf); int tmp=en; for(i=1;i<=n;++i) if(d[i]>0) ins(ss,i,d[i]); else if(d[i]<0) ins(i,tt,-d[i]); dinic(ss,tt); ans=e[tmp].w; for(i=hr[ss];i;i=e[i].nex) e[i].w=e[i^1].w=0; for(i=hr[tt];i;i=e[i].nex) e[i].w=e[i^1].w=0; e[tmp^1].w=e[tmp].w=0; ans-=dinic(t,s); printf("%d\n",ans);}
无源汇上下界最小/大费用可行流
模型
在无源汇上下界可行流的基础上，要求费用最小/大。
思路
每条边的费用是不变的，和虚拟源汇的边费用是\(0\)
把跑最大流改为跑最小/大费用最大流
Code
咕咕咕
无源汇上下界最小/大费用可行流
模型
在有源汇上下界可行流的基础上，要求费用最小/大。
思路
每条边的费用是不变的，和虚拟源汇的边费用是\(0\)
把跑最大流改为跑最小/大费用最大流
Code
/* 有源汇上下界最小费用可行流 [AHOI2014/JSOI2014]支线剧情 */#include#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define reg registerinline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}const int MN=305,inf=0x3f3f3f3f;struct edge{int to,w,c,nex;}e[MN*MN<<1];int hr[MN],en=1;inline void ins(int x,int y,int w,int c){ e[++en]=(edge){y,w,c,hr[x]};hr[x]=en; e[++en]=(edge){x,0,-c,hr[y]};hr[y]=en;}std::queue q;int S,T,d[MN];bool inq[MN];bool spfa(){ memset(d,0x3f,sizeof d); memset(inq,0,sizeof inq); q.push(T);d[T]=0;inq[T]=true; while(!q.empty()) { int u=q.front();q.pop();inq[u]=false; for(int i=hr[u];i;i=e[i].nex) if(d[e[i].to]>d[u]+e[i^1].c&&e[i^1].w) { d[e[i].to]=d[u]+e[i^1].c; if(!inq[e[i].to]) inq[e[i].to]=true,q.push(e[i].to); } } return d[S]!=inf;}bool vis[MN];int mincost;int dfs(int x,int f){ vis[x]=true; if(x==T) return f; int used=0; for(int i=hr[x];i;i=e[i].nex) if(d[e[i].to]==d[x]-e[i].c&&e[i].w&&!vis[e[i].to]) { int tmp=dfs(e[i].to,min(f-used,e[i].w)); e[i].w-=tmp;e[i^1].w+=tmp;used+=tmp; mincost+=tmp*e[i].c; if(used==f) return f; } return used;}int flow(){ while(spfa()) { do { memset(vis,0,sizeof vis); dfs(S,inf); }while(vis[T]); } return mincost;}int n,h[MN],ans;int main(){ n=read();S=n+2;T=n+3; reg int i,j,k,l; for(i=1;i<=n;++i) { j=read();h[i]-=j; while(j--) ++h[k=read()],ans+=(l=read()),ins(i,k,inf,l); } for(i=2;i<=n;i++) ins(i,n+1,inf,0);ins(n+1,1,inf,0); for(i=1;i<=n;++i) if(h[i]>0) ins(S,i,h[i],0); else ins(i,T,-h[i],0); printf("%d\n",ans+flow());}
Blog来自PaperCloud，未经允许，请勿转载，TKS！