Templates for XCPC - 网络流

Dinic 求最大流

int dep[N],cur[N],flow[M];
bool bfs(){
    queue<int> Q;
    memset(dep,0,sizeof(int)*(V+1));
    dep[S]=1;
    Q.push(S);
    while(Q.size()){
        int u=Q.front();Q.pop();
        for(int i=frm[u];i;i=nxt[i]){
            int v=to[i];
            if(!dep[v]&&cap[i]>flow[i]){
                dep[v]=dep[u]+1;
                Q.push(v);
            }
        }
    }
    return dep[T];
}
int dfs(int u,int f){
    if(u==T||!f)return f;
    int ret=0;
    for(int &i=cur[u];i;i=nxt[i]){
        int v=to[i];
        int d;
        if(dep[v]==dep[u]+1&&(d=dfs(v,min(f-ret,cap[i]-flow[i])))){
            flow[i]+=d;
            flow[i^1]-=d;
            ret+=d;
            if(ret==f)break;
        }
    }
    return ret;
}
int dinic(){
    int maxflow=0;
    while(bfs()){
        memcpy(cur,frm,sizeof(int)*(V+1));
        maxflow+=dfs(S,INF);
    }
    return maxflow;
}

最小割

直观上最小割就是用最小代价切断 s 到 t 的所有通路。最大流最小割定理：最小割等于最大流。原图中所有从 S 到 T 的满流边，就是最小割边。

最小费用最大流

int n,m;
int frm[N],nxt[M],to[M],cap[M],cost[M],flow[M],_=1;
int dis[N],pre[N],vis[N];
int S,T,V;
void add_edge(int u,int v,int w,int c){
    nxt[++_]=frm[u];frm[u]=_;to[_]=v;cap[_]=w;cost[_]=c;
    nxt[++_]=frm[v];frm[v]=_;to[_]=u;cap[_]=0;cost[_]=-c;
}
bool spfa(){
    queue<int> Q;
    fill(dis,dis+V+1,INF);
    memset(vis,0,sizeof(int)*(V+1));
    memset(pre,0,sizeof(int)*(V+1));
    dis[S]=0;vis[S]=1;Q.push(S);
    while(Q.size()){
        int u=Q.front();Q.pop();vis[u]=0;
        for(int i=frm[u];i;i=nxt[i]){
            int v=to[i];
            if(cap[i]>flow[i]&&dis[v]>dis[u]+cost[i]){
                dis[v]=dis[u]+cost[i];pre[v]=i;
                if(!vis[v]){vis[v]=1;Q.push(v);}
            }
        }
    }
    return pre[T];
}
pair<int,int> mcmf(){
    int maxflow=0,mincost=0;
    while(spfa()){
        int d=INF;
        for(int i=pre[T];i;i=pre[to[i^1]]){
            d=min(d,cap[i]-flow[i]);
        }
        for(int i=pre[T];i;i=pre[to[i^1]]){
            flow[i]+=d;
            flow[i^1]-=d;
            mincost+=d*cost[i];
        }
        maxflow+=d;
    }
    return {maxflow,mincost};
}

最小费用上下界可行流

默认无源汇，若需要有源汇可以连一条 T 到 S ，容量为无穷大、费用为 $0$ 的边。

void add_bound_edge(int u,int v,int l,int r,int c){
    add_edge(u,v,r-l,c);
    d[u]-=l;d[v]+=l;
    base_cost+=l*c;
}
pair<bool,int> mcff(){
    SS=V+1;TT=V+2;
    S=SS;T=TT;V=V+2;
    int need=0;
    for(int i=1;i<=V;i++){
        if(d[i]>0){
            add_edge(SS,i,d[i],0);
            need+=d[i];
        }
        else if(d[i]<0){
            add_edge(i,TT,-d[i],0);
        }
    }
    auto res=mcmf();
    if(res.first!=need){
        return {false,0};
    }
    return {true,base_cost+res.second};
}