网络流

EricQian · 2019-12-02 21:41:42 · 个人记录

最大流

P3376 【模板】网络最大流

P4722 【模板】最大流加强版 / 预流推进

1.\operatorname{EK} 算法

复杂度：O(nm^2)

所以，关于 \operatorname{EK} ，他死了

#define Maxn 205
#define Maxm 5005
#define inf 0x7f7f7f7f
int n,m,sum=0,tot=1;
int pre[Maxn],ds[Maxn],hea[Maxn],ver[Maxm],nex[Maxm],edg[Maxm];
bool vis[Maxn];
bool dfs(int s,int t)
{
     memset(vis,false,sizeof(vis));
     queue<int> q; q.push(s),vis[s]=1,ds[s]=inf;
     while(!q.empty())
     {
         int cur=q.front(); q.pop();
         for(int i=hea[cur];i;i=nex[i]) if(edg[i] && !vis[ver[i]])
             {
                 pre[ver[i]]=i,vis[ver[i]]=true;
                 ds[ver[i]]=min(ds[cur],edg[i]);
                 if(ver[i]==t) return true;
                 q.push(ver[i]);
             }
     }
     return false;
}
void EK(int s,int t)
{
     while(dfs(s,t))
     {
         int x=t;
         while(x!=s)
         {
             int i=pre[x];
             edg[i]-=ds[t],edg[i^1]+=ds[t];
             x=ver[i^1];
         }
         sum+=ds[t];
     }
}
EK(s,t);

2.\operatorname{dinic} 算法

1. 多路增广： 每次增广前，我们先用 BFS 来将图分层,建立残量网络。设源点的层数为 0 ，那么一个点的层数便是它离源点的最近距离。

2. 当前弧优化： 如果一条边已经被增广过，那么它就没有可能被增广第二次。那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边。

实现：在建立残量网络的时候对 cur[] 进行初始化，表示这一轮寻找曾增广路的 tmphead[] ：

for(int i=1;i<=n;i++) cur[i]=hea[i];

之后再每一次寻找增广路的 dinic 函数中进行一下操作：

for(int i=cur[u];i && rest;i=nex[i])
{
     cur[u]=i;
     ... 
}

最坏复杂度为 O(n^2m) （一般跑不到这个上界），而在二分图网络中，复杂度可以达到 O(\sqrt{n}m)

所以，关于 \operatorname{Dinic} 他快死了。

核心代码：

#define inf 0x7f7f7f7f
#define Maxn 205
#define Maxm 5005
int n,m,s=201,t=202,tot=1;
int hea[Maxn],tmphea[Maxn],nex[Maxm<<1],ver[Maxm<<1],edg[Maxm<<1];
int dep[Maxn],que[Maxn],ql,qr;
ll sum;
void add(int x,int y,int d)
{
     ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d;
     ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot,edg[tot]=0;
}
bool bfs()
{
     memset(dep,0,sizeof(dep)),dep[s]=1;
     que[ql=qr=1]=s;
     while(ql<=qr)
     {
         int cur=que[ql++];
         for(int i=hea[cur];i;i=nex[i]) if(edg[i] && !dep[ver[i]])
             dep[ver[i]]=dep[cur]+1,que[++qr]=ver[i];
     }
     memcpy(tmphea,hea,sizeof(hea));
     return dep[t];
}
int dinic(int x,int flow)
{
     if(x==t) return flow;
     int rest=flow;
     for(int i=tmphea[x],tmp;i && rest;i=nex[i])
     {
         tmphea[x]=i;
         if(edg[i] && dep[ver[i]]==dep[x]+1)
         {
             if(!(tmp = dinic(ver[i],min(rest,edg[i])))) dep[ver[i]]=0;
             edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp;
         }
     }
     return flow-rest;
}

int flow;
while(bfs()) while(flow=dinic(s,inf)) sum+=1ll*flow;
printf("%lld\n",sum);

3.\operatorname{ISAP}

该优化被称为 GAP 优化

咕咕咕

4.\operatorname{Push-Relabel} 预流推进算法

咕咕咕

5.\operatorname{HLPP} 算法

复杂度：O(n^2\sqrt m)

咕咕咕

费用流

P3381 【模板】最小费用最大流

1.\operatorname{EK}

也叫做 \operatorname{MCMF} 算法

#define Maxn 5005
#define Maxm 50005
#define inf 0x7f7f7f7f
int n,m,sum,hua,tot=1;
int hea[Maxn],ver[Maxm*2],nex[Maxm*2],edg[Maxm*2],Cos[Maxm*2];
int pre[Maxn],ds[Maxn],liu[Maxn];
bool inq[Maxn];
bool spfa(int s,int t)
{
     memset(ds,inf,sizeof(ds)),memset(liu,inf,sizeof(liu)),memset(inq,false,sizeof(inq));
     queue<int> q; q.push(s),ds[s]=0,inq[s]=true,pre[t]=-1;
     while(!q.empty())
     {
         int cur=q.front(); q.pop(),inq[cur]=false;
         for(int i=hea[cur];i;i=nex[i]) if(edg[i]>0 && ds[vis]>ds[cur]+Cos[i] && ds[cur]+Cos[i]>=0)
         {
             liu[ver[i]]=min(liu[cur],edg[i]);
             pre[ver[i]]=i,ds[ver[i]]=ds[cur]+Cos[i];
             if(!inq[ver[i]]) inq[ver[i]]=true,q.push(ver[i]);
         }
     }
     return pre[t]!=-1;
}
void EK(int s,int t)
{
     while(spfa(s,t))
     {
         int x=t;
         while(x!=s)
         {
             int i=pre[x];
             edg[i]-=liu[t],edg[i^1]+=liu[t];
             x=ver[i^1];
         }
         hua+=ds[t]*liu[t];
         sum+=liu[t];
     }
}

EK(s,t);
printf("%d %d\n",sum,hua);

2.\operatorname{dinic}（类 \operatorname{dinic} 算法）

只用将 DFS 改为 \operatorname{SPFA} 就可以了，将记录深度的 d 数组变为 ds ，选取增广路的之后判断改为：

if(... && ds[ver[i]]==ds[u]+Cost[i]) ...

注意加上当前弧优化，复杂度为 O(nmf) ，其中 f 为流量。

核心代码：

#define Maxn 5005
#define Maxm 50005
#define inf 0x7f7f7f7f
bool spfa()
{
     memset(ds,inf,sizeof(ds)),memcpy(tmphea,hea,sizeof(hea));
     queue<int> q; q.push(s),ds[s]=0,inq[s]=true;
     while(!q.empty())
     {
         int cur=q.front(); q.pop(),inq[cur]=false;
         for(int i=hea[cur];i;i=nex[i]) if(edg[i]>0 && ds[ver[i]]>ds[cur]+Cost[i])
         {
             ds[ver[i]]=ds[cur]+Cost[i];
             if(!inq[ver[i]]) inq[ver[i]]=true,q.push(ver[i]);
         }
     }
     return ds[t]!=inf;
}
int dinic(int x,int flow)
{
     if(x==t) return flow;
     int rest=flow; inq[x]=true;
     for(int i=tmphea[x];i && rest;i=nex[i])
     {
         tmphea[x]=i;
         if(!inq[ver[i]] && edg[i]>0 && ds[ver[i]]==ds[x]+Cost[i])
         {
             int tmp=dinic(ver[i],min(rest,edg[i]));
             if(!tmp) ds[ver[i]]=0;
             sum_cos+=1ll*Cost[i]*tmp,edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp; 
         }
     }
     inq[x]=false; return flow-rest;
}

int flow;
while(spfa()) while(flow=dinic(s,inf)) sum_liu+=1ll*flow;

最小割

给定一个网络 G=(V,E) ，源点和汇点为 S 和 T ，若删去边集 E'\subseteq E ，使得 S 和 T 不连通，则该边集成为网络的割。边的容量值和最小的割成为该网络的最小割。

\text{最小割} = \text{最大流}