Acm
5 Aug 2019

最大流

假设_G_(V,E) 是一个有限的有向图,它的每条边(u,v)∈E都有一个非负值实数的容量_c_(u,v) 。如果(u,v)不属于E,我们假设_c_(u,v) = 0 。我们区别两个顶点:一个源点s_和一个汇点_t。一道网络流是一个对于所有结点_u_和_v_都有以下特性的实数函数f:V×V→R

容量限制 (Capacity Constraints):

f(u,v)≤c(u,v)一条边的流不能超过它的容量。

斜对称 (Skew Symmetry):

f(u,v)=-f(v,u)由_u_到_v_的净流必须是由_v_到_u_的净流的相反(参考例子)。(既然要看网络流,这是一定要知道的)

流守恒 (Flow Conservation):

除非_u_=s_或_u=t,否则Σ(w∈V)f(u,w)=0 一结点的净流是零,除了“制造”流的源点和“消耗”流的汇点。

注意_f_(u,v) 是由_u_到_v_的_净_流。如果该图代表一个实质的网络,由_u_到_v_有 4 单位的实际流及由_v_到_u_有 3 单位的实际流,那么_f_(u,v) = 1 及_f_(v,u) = − 1。

边的剩余容量 (Residual Capacity)是_cf_(u,v) =c(u,v)−f(u,v)。这定义了以_Gf_(V,Ef)表示的剩余网络 (Residual Network),它显示可用的容量的多少。留意就算在原网络中由_u_到_v_没有边,在剩余网络乃可能有由_u_到_v_的边。因为相反方向的流抵消,减少由v到u的流等于增加由_u_到_v_的流。扩张路径 (Augmenting Path)是一条路径 (u1,u2…uk),而_u_1 =suk=t_及_cf(ui,ui+ 1) > 0,这表示沿这条路径传送更多流是可能的。

以上摘自百度百科

下面求最大流的两个算法基础思路都一样,就是求不断增广路。增广路是一条从s到t的路径,且上面的每一条边的剩余容量大于0。每求出一条增广路及其最小流量都要在这条路径上更新剩余流量,并将最小流量加到最大流中。

将每一条边的反向边也连起来,因为斜对称性,所以每次更新时,除了在边上减去增广路的最小流量,还要在反向边上加上最小流量。

至于为什么是对的。。。我还需要一段时间的沉淀来理解。。



Edmonds-Karp

直接在一张图上不断寻找增广路,然后不断更新。。

O(nm^2) 1e2 ~ 1e3

POJ - 1273 Drainage Ditches

int head[N],ver[N*2],edge[N*2],Next[N*2],tot=1;
void add(int x,int y,int w){
    ver[++tot]=y,edge[tot]=w;
    Next[tot]=head[x],head[x]=tot;
}
int n,m,s,t,maxflow,v[N],incf[N],pre[N];
bool bfs(){
    memset(v,0,sizeof(v));
    queue<int> Q;
    Q.push(s),v[s]=1;
    incf[s]=inf;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!edge[i]||v[y])continue;
            incf[y]=min(incf[x],edge[i]);
            pre[y]=i,v[y]=1,Q.push(y);
            if(y==t)return true;
        }
    }
    return false;
}
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 resetMaxflow(){
    memset(head,0,sizeof(head));
    tot=1,maxflow=0;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>m>>n){
        resetMaxflow();s=1,t=n;
        for(int i=1;i<=m;i++){
            int x,y,z;
            cin>>x>>y>>z;
            add(x,y,z),add(y,x,0);
        }
        while(bfs())update();
        cout<<maxflow<<endl;
    }
}



Dinic

每次都遍历一整张图显然是可以继续优化的。

不断求出分层图,通过dfs求增广路并更新。

O(nm^2) 1e3 ~ 1e4

P3376 【模板】网络最大流

int head[N],ver[N*2],edge[N*2],Next[N*2],tot=1;
void add(int x,int y,int w){
    ver[++tot]=y,edge[tot]=w;
    Next[tot]=head[x],head[x]=tot;
}
int n,m,s,t,maxflow,d[N];
bool bfs(){
    queue<int> Q;
    memset(d,0,sizeof(d));
    Q.push(s),d[s]=1;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!edge[i]||d[y])continue;
            Q.push(y),d[y]=d[x]+1;
            if(y==t)return true;
        }
    }
    return false;
}
int dinic(int x,int flow){
    if(x==t)return flow;
    int rest=flow,k;
    for(int i=head[x];i&&rest;i=Next[i]){
        int y=ver[i];
        if(!edge[i]||d[y]!=d[x]+1)continue;
        k=dinic(y,min(rest,edge[i]));
        if(!k)d[y]=0;
        edge[i]-=k,edge[i^1]+=k;
        rest-=k;
    }
    return flow-rest;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z),add(y,x,0);
    }
    int flow=0;
    while(bfs())
        while(flow=dinic(s,inf))
            maxflow+=flow;
    cout<<maxflow<<endl;
}

Tags: