8-网络流.md

8-网络流

最大流

dinic

初始化 g.init(s,t,num)

先通过bfs对残余网络进行分层

根据层次反复 dfs遍历残量网络，一次 dfs找到一条增广路并更新，直至跑完能以当前层次到达 TT 的所有路径。

一般可解决1e5以内问题

const int V = 1010;
const int E = 101000;
template<typename T>
struct FlowGraph{
    int s,t,vtot;
    int head[V],etot;
    int dis[V],cur[V];
    struct edge{
        int v,nxt;
        T f;
    }e[E*2];
    void addedge(int u,int v,T f){
        e[etot] = {v,head[u],f};head[u] = etot++;
        e[etot] = {u,head[v],0};head[v] = etot++;
    }
    bool bfs(){
        for(int i=1;i<=vtot;i++){
            dis[i]=0;
            cur[i] = head[i];
        }
        queue<int>q;
        q.push(s);dis[s]=1;
        while(!q.empty()){
            int u = q.front();q.pop();
            for(int i=head[u];~i;i = e[i].nxt){
                if(e[i].f&&!dis[e[i].v]){
                    int v = e[i].v;
                    dis[v] = dis[u]+1;
                    if(v==t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }
    T dfs(int u,T m){
        if(u==t) return m;
        ll flow = 0;
        for(int i=cur[u];~i;cur[u]=i=e[i].nxt)//当前弧优化
            if(e[i].f&&dis[e[i].v]==dis[u]+1){
                T f = dfs(e[i].v,min(m,e[i].f));
                e[i].f-=f;
                e[i^1].f+=f;
                m-=f;
                flow+=f;
                if(!m) break;
            }
        if(!flow) dis[u] = -1;
        return flow;
    }
    T dinic(){
        T flow = 0;
        while(bfs()) flow+=dfs(s,numeric_limits<T>::max());
        return flow;
    }
    void init(int s_,int t_,int vtot_){
        s = s_;
        t = t_;
        vtot = vtot_;
        etot = 0;
        for(int i=1;i<=vtot;i++){
            head[i]=-1;
        }
    }
};
FlowGraph<ll>g;
int n,m,s,t;//s  源点  t  汇点
void solve()
{   cin>>n>>m>>s>>t;
    g.init(s,t,n);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g.addedge(u,v,w);
    }
    cout<<g.dinic()<<endl;
}

建模思想

拆点

若某些点只允许通过一定次数x

则可将这些点拆成两个点,建一条边从一个点连向另一个点，流量为次数x

超级源点汇点

建一个抽象的s,t

最小流

将都是正的边权改成负的，于是求出了最小流

最小割

最小割的容量等于最大流

割完后分为S、T两个点集合

S集合中的点i满足残量网络中源点s能到i，即dis[i]!=0

费用流

最小费用最大流一般比最大流多个属性（？

比如：

有 n件工作要分配给 n个人做。第 i个人做第 j件工作产生的效益为 cij 。试设计一个将 n 件工作分配给 n个人做的分配方案，使产生的总效益最小或最大。

一条s到t的流即表示经过的工作给经过的人做，产生的费用即为效益

则能求出最小的总效益

求最大效益时只需将费用改为负的效益，则得解(要求初始图中无负环，否则spfa会寄)

板子：

将代价视为边的距离，先通过spfa求出s到t的最短路，再在该路进行增广

const int V = 20100;
const int E = 201000;
template<typename T>
struct MinCostGraph{
    int s,t,vtot;
    int head[V],etot;
    T dis[V],flow,cost;
    int pre[V];
    bool vis[V];

    struct edge{
        int v,nxt;
        T f,c;
    }e[E*2];
    void addedge(int u,int v,T f,T c,T f2=0){
        e[etot] = {v,head[u],f,c};head[u] = etot++;
        e[etot] = {u,head[v],f2,-c};head[v] = etot++;
    }
    bool spfa(){
        T inf = numeric_limits<T>::max()/2;
        for(int i=1;i<=vtot;i++){
            dis[i]=inf;
            vis[i] = false;
            pre[i] = -1;
        }
        dis[s] = 0;
        vis[s] = true;
        queue<int>q;
        q.push(s);
        while(!q.empty()){
            int u = q.front();
            for(int i=head[u];~i;i = e[i].nxt){
                int v = e[i].v;
                if(e[i].f&&dis[v]>dis[u]+e[i].c){
                    dis[v] = dis[u]+e[i].c;
                    pre[v] = i;
                    if(!vis[v]){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
            q.pop();
            vis[u] = false;
        }
        return dis[t]!=inf;
    }
    void augment(){
        int u = t;
        T f = numeric_limits<T>::max();
        while(~pre[u]){
            f = min(f,e[pre[u]].f);
            u = e[pre[u]^1].v;
        }
        flow+=f;
        cost+=f*dis[t];
        u = t;
        while(~pre[u]){
            e[pre[u]].f-=f;
            e[pre[u]^1].f+=f;
            u = e[pre[u]^1].v;
        }
    }
    pair<T,T> solve(){
        flow=0;cost=0;
        while(spfa()) augment();
        return {flow,cost};
    }
    void init(int s_,int t_,int vtot_){
        s = s_;
        t = t_;
        vtot = vtot_;
        etot = 0;
        for(int i=1;i<=vtot;i++){
            head[i]=-1;
        }
    }
};
MinCostGraph<ll>g;
int n,m,s,t;
void solve()
{   cin>>n>>m>>s>>t;
    g.init(s,t,n);
    for(int i=1;i<=m;i++){
        int u,v,w,c;
        cin>>u>>v>>w>>c;
        g.addedge(u,v,w,c);
    }
    pair<ll,ll> ans = g.solve();
    cout<<ans.first<<" "<<ans.second<<endl;
}