网络流
luckydrawbox · · 个人记录
浅谈网络流的各种建模方法
最大流
由于其他算法并不常用，所以这里只给出
Dinic
常量与变量
函数
代码
struct Dinic{
const ll INF=0x3f3f3f3f3f3f3f3f;
int head[N],ver[M<<1],nxt[M<<1],tot=1;
ll edge[M<<1];
void add(int x,int y,ll z){
ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
ll maxflow;
int S,T,d[N],now[N];
queue<int>q;
bool bfs(){
memset(d,0,sizeof(d));
while(q.size())q.pop();
q.push(S);d[S]=1;now[S]=head[S];
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x],y;i;i=nxt[i]){
y=ver[i];
if(edge[i]&&!d[y]){
q.push(y);now[y]=head[y];
d[y]=d[x]+1;
if(y==T)return 1;
}
}
}
return 0;
}
ll dinic(int x,ll flow){
if(x==T)return flow;
ll rest=flow;
for(int i=now[x],k,y;i&&rest;i=nxt[i]){
y=ver[i];now[x]=i;
if(edge[i]&&d[y]==d[x]+1){
k=dinic(y,min(rest,edge[i]));
if(!k)d[y]=0;
edge[i]-=k;edge[i^1]+=k;
rest-=k;
}
}
return flow-rest;
}
void solve(){
ll flow=maxflow=0;
while(bfs())while(flow=dinic(S,INF))maxflow+=flow;
}
}mf;Edmonds-Karp 动能算法
代码
const ll INF=1ll<<60;
int n,m,s,t,pre[N];
int head[N],nxt[M<<1],ver[M<<1],tot=1;
ll incf[N],edge[M<<1],maxflow=0;
bool v[N];
void add(int x,int y,ll z){
ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
bool fk_bfs(){
memset(v,0,sizeof(v));
queue<int>q;
q.push(s);
v[s]=1;
incf[s]=INF;
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i])
if(edge[i]){
int y=ver[i];
if(v[y])
continue;
incf[y]=min(incf[x],edge[i]);
pre[y]=i;
v[y]=1;
q.push(y);
if(y==t)
return 1;
}
}
return 0;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
edge[i]-=incf[t];
edge[i^1]+=incf[t];
x=ver[i^1];
}
maxflow+=incf[t];
}
void fk(){
while(fk_bfs())
update();
}Highest Label Preflow Push 最高标号预流推进算法
代码
int n,m,s,t;
int head[N],nxt[M<<1],ver[M<<1],edge[M<<1],tot=1;
int cnt=1,h[N],rest[N],gap[N],hest=0;
stack<int>B[N];
void add(int x,int y,ll z){
ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
int push(int x){
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],z=edge[i];
if(z&&(x==s||h[x]==h[y]+1)){
int k=(x==s)?z:min(z,rest[x]);
if(y!=s&&y!=t&&!rest[y]){
B[h[y]].push(y);
hest=max(hest,h[y]);
}
rest[x]-=k;
rest[y]+=k;
edge[i]-=k;
edge[i^1]+=k;
if(!rest[x])
return 0;
}
}
return 1;
}
void relabel(int x){
h[x]=h[0];
for(int i=head[x];i;i=nxt[i])
if(edge[i])
h[x]=min(h[x],h[ver[i]]);
if(++h[x]<n){
B[h[x]].push(x);
hest=max(hest,h[x]);
gap[h[x]]++;
}
}
bool bfs(){
memset(h,0x3f,sizeof(h));
queue<int>q;
q.push(t);
h[t]=0;
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i])
if(edge[i^1]&&h[ver[i]]>h[x]+1){
h[ver[i]]=h[x]+1;
q.push(ver[i]);
}
}
return h[s]!=h[0];
}
int select(){
while(!B[hest].size()&&hest>=0)
hest--;
return hest==-1?0:B[hest].top();
}
int hlpp(){
if(!bfs())
return 0;
memset(gap,0,sizeof(gap));
for(int i=1;i<=n;i++)
if(h[i]!=h[0])
gap[h[i]]++;
h[s]=n;
push(s);
int x;
while(x=select()){
B[hest].pop();
if(push(x)){
if(!(--gap[h[x]]))
for(int i=1;i<=n;i++)
if(i!=s&&i!=t&&h[i]>h[x]&&h[i]<n+1)
h[i]=n+1;
relabel(x);
}
}
return rest[t];
}最小费用最大流
SSP 算法
常量与变量
函数
代码
struct Dinic{
const ll INF=0x3f3f3f3f3f3f3f3f;
int head[N],ver[M<<1],nxt[M<<1],tot=1;
ll edge[M<<1],cost[M<<1],dis[N],mxflow,micost;
void add(int x,int y,ll z,ll w){
ver[++tot]=y,edge[tot]=z,cost[tot]=w,nxt[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,cost[tot]=-w,nxt[tot]=head[y],head[y]=tot;
}
queue<int>q;
int v[N],now[N],d[N],S,T;
bool spfa(){
memset(dis,0x3f,sizeof(dis));
memset(v,0,sizeof(v));
while(q.size())q.pop();
q.push(S);dis[S]=0;d[S]=v[S]=1;now[S]=head[S];
while(q.size()){
int x=q.front();q.pop();
v[x]=0;
for(int i=head[x],y;i;i=nxt[i]){
y=ver[i];
if(edge[i]&&dis[y]>dis[x]+cost[i]){
dis[y]=dis[x]+cost[i];
d[y]=d[x]+1;
if(!v[y]){
q.push(y);
v[y]=1;now[y]=head[y];
}
}
}
}
return dis[T]!=INF;
}
ll dinic(int x,ll flow){
if(x==T)return flow;
ll rest=flow,k;
for(int i=now[x],y;i&&rest;i=nxt[i]){
y=ver[i];now[x]=i;
if(edge[i]&&dis[y]==dis[x]+cost[i]&&d[y]==d[x]+1){
k=dinic(y,min(edge[i],rest));
if(!k)d[y]=0;
edge[i]-=k;edge[i^1]+=k;
rest-=k;micost+=k*cost[i];
}
}
return flow-rest;
}
void solve(){
ll flow=mxflow=micost=0;
while(spfa())while(flow=dinic(S,INF))mxflow+=flow;
}
}mf;有源汇上下界最小费用最大流
struct lrDinic{
const ll INF=0x3f3f3f3f3f3f3f3f;
int head[N],ver[M<<1],nxt[M<<1],tot=1,te=0;
ll edge[M<<1],cost[M<<1],dis[N],mxflow,micost,resflow,rescost;
ll in[N],out[N];
void add(int x,int y,ll z,ll w,ll z0=0){
ver[++tot]=y,edge[tot]=z,cost[tot]=w,nxt[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=z0,cost[tot]=-w,nxt[tot]=head[y],head[y]=tot;
}
struct Edge{
int x,y;
ll l,r,w;
}e[M<<1];
queue<int>q;
int v[N],now[N],d[N],S,T,rS,rT;
void clear(){
memset(head,0,sizeof(head));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
tot=1;te=0;S=T=rS=rT=0;
}
bool spfa(){
memset(dis,0x3f,sizeof(dis));
memset(v,0,sizeof(v));
while(q.size())q.pop();
q.push(S);dis[S]=0;d[S]=v[S]=1;now[S]=head[S];
while(q.size()){
int x=q.front();q.pop();
v[x]=0;
for(int i=head[x],y;i;i=nxt[i]){
y=ver[i];
if(edge[i]&&dis[y]>dis[x]+cost[i]){
dis[y]=dis[x]+cost[i];
d[y]=d[x]+1;
if(!v[y]){
q.push(y);
v[y]=1;now[y]=head[y];
}
}
}
}
return dis[T]!=INF;
}
ll dinic(int x,ll flow){
if(x==T)return flow;
ll rest=flow,k;
for(int i=now[x],y;i&&rest;i=nxt[i]){
y=ver[i];now[x]=i;
if(edge[i]&&dis[y]==dis[x]+cost[i]&&d[y]==d[x]+1){
k=dinic(y,min(edge[i],rest));
if(!k)d[y]=0;
edge[i]-=k;edge[i^1]+=k;
rest-=k;micost+=k*cost[i];
}
}
return flow-rest;
}
void solve(){
ll flow=mxflow=micost=0;
while(spfa())while(flow=dinic(S,INF))mxflow+=flow;
}
bool work(){
e[++te]={rT,rS,0,INF,0};
int n=0;
ll sum=0;resflow=0;rescost=0;
int bk;
for(int i=1;i<=te;i++){
add(e[i].x,e[i].y,e[i].r-e[i].l,e[i].w);
out[e[i].x]+=e[i].l;
in[e[i].y]+=e[i].l;
n=max(n,max(e[i].x,e[i].y));
rescost+=e[i].l*e[i].w;
}
bk=tot;
S=n+1,T=n+2;
for(int i=1;i<=n;i++){
ll c=in[i]-out[i];
if(c>0)add(S,i,c,0),sum+=c;
if(c<0)add(i,T,-c,0);
}
solve();
resflow+=edge[bk];
rescost+=micost;
if(mxflow!=sum)return 0;
edge[bk]=edge[bk^1]=0;
S=rS,T=rT;
solve();
resflow+=mxflow;
rescost+=micost;
return 1;
}
}mf;