跳转至

最小割

Dinic 算法

363 网络流 最小割 Dinic 算法_哔哩哔哩_bilibili

image.png

注：容易划分均可

image.png

如上图。左边为\(S\)，右边为\(T\)，\(c(S,T)=7+6\)即1→2和1→4的容量和，不包括从\(T\)到\(S\)的（即5→1）

image.png

如上图。左边为\(S\)，右边为\(T\)，\(c(S,T)=2+1+2\)即2→3和2→5和4→5的容量和，不包括从\(T\)到\(S\)的（即5→1）

最大流最小割定理

$f(s,t){max}=c(S,T) $

最小割 最小割就是求得一个割\((S,T)\)，使得割的容量\(c(s,t)\)最小。 最小割的方案往往并不是唯一的。

即：最大流的流量=最小割的容量

图中文字如下：

证明：假设最小割<最大流，割断一些边后，网络流还没有达到最大，还可以找到s到t的增广路，这与割的定义矛盾.故最小割≥最大流。

给出一个 最小割=最大流的构造方案即可。求出最大流后，从源点开始对残留网DFS，标记能够到达的点，则标记的点构成S集合，未标记的点构成T集合。此割就是最小割。

请思考证明！

三个问题：

  1. 求最小割

  2. 求最小割的划分

  3. 求最小割的最少边数

Q1 求最小割

其实就是求最大流，模板即可

Q2

在求完最大流后 对残留网进行dfs

void mincut(int u){
    vis[u]=1;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(!vis[v])&&e[i].c){mincut(v);}
    }
}

扫描后被标记的点就是\(S\)部分，否则就是\(T\)部分

Q3

将正边为1，反向边为0，再次运行一遍dinic

//a[],b[]记录输入的点对
idx=1;
memset(h,0,sizeof h);
for(int i=1;i<=m;i++){
    add(a[i],b[i],1);
    add(b[i],a[i],0);
}
cout<<dinic()<<endl;

例题 #1 [USACO4.4] 追查坏牛奶 Pollutant Control

题目描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。

很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。

送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。

你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

输入格式

第 \(1\) 行两个整数 \(N\)、\(M\)，\(N\) 表示仓库的数目，\(M\) 表示运输卡车的数量。仓库 \(1\) 代表发货工厂，仓库 \(N\) 代表有三聚氰胺的牛奶要发往的零售商。

第 \(2\sim M+1\) 行，每行 \(3\) 个整数 \(S_i\)、\(E_i\) 和 \(C_i\)。其中 \(S_i\)、\(E_i\) 分别表示这辆卡车的出发仓库和目的仓库。\(C_i\) 表示让这辆卡车停止运输的损失。

输出格式

两个整数 \(C\) 和 \(T\)，\(C\) 表示最小的损失，\(T\) 表示在损失最小的前提下，最少要停止的卡车数。

对于 \(100 \%\) 的数据，满足 \(2 \le N \le 32\)，\(0 \le M \le 10^3\)，\(1 \le S_i \le N\)，\(1 \le E_i \le N\)，\(0 \le C_i \le 2 \times 10^6\)。

题目翻译来自 NOCOW。

USACO Training Section 4.4

因为本题既要输出最小割的值又要输出割的边数，前者好求关键是后者如何去求更简单，容易想到我们可以直接建两次图，一次按原边权建图跑最大流求得最小割，再按边权为1建图跑最大流求割的边数，这是一种思路;

当然我们完全可以换种思路用一次最大流搞定，只需建图时将边权\(w=w\times a+1\)（w为本来的边权，a为大于1000的数），这样我们能求得最大流ans，则最小割的值为ans/a，割的边数为ans%a。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
int mf[N];//最大流量maxflow 
int s,t,pre[N],n,m,u,v,w;
struct edge{
    int v,c,nxt;
}e[20*N];
int h[N],idx=1;//边的id从2开始存,因为边与残留边对应,使用i^1可以迅速在n与n+1之间相互转换(n为偶数),不用特判 
void add(int a,int b,int c){
    e[++idx]={b,c,h[a]};
    h[a]=idx;
}
bool bfs(){//找一条可以从s到t的有效路径 
    memset(mf,0,sizeof mf);//将每个点的流量上限变成0
    queue<int> q;
    q.push(s);mf[s]=1e9;//源点的流量上限为无穷大,即源点能为后面提供无限大的流量 
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nxt){//扫描出边 
            int v=e[i].v;
            if(!mf[v]&&e[i].c){//如果 没有访问过v(在本轮bfs中,即碰到环不走回头路)并且存在这条边/这条边在之前走过但还有空余容量(容量>0) 
                //***重要 
                mf[v]=min(mf[u],e[i].c);//更新流量上限为之前更新过的可以到达u的流量(即点u能提供的最大流量)与u-v见之间的容量的min 
                pre[v]=i; //存目前路径上点v的前驱边
                //***
                q.push(v);
                if(v==t)return 1;//说明找到了一条增广路 
                 //找增光路相当于找到一条新的流量到t,回顾二分图的增光路,之前已经找到的增光路的路径可以调整,但流量不会变化(即不会使之前已经有的流量减小) 
            }
        }
    }
    return 0;
} 
int EK(){
    int nf=0;//当前流量nowflow 
    while(bfs()){//新找到一条增广路,路的流量为mf[t] (流量是从s开始在到达t途中受到限制逐渐减小的,因此到达t的流量才是这条路的流量)
        int v=t;
        while(v!=s){//从t往回在更新残留网 
            int i=pre[v];
            //***重要 
            e[i].c-=mf[t];//主边,空余的容量减少了 
            e[i^1].c+=mf[t];//残留边(反向边) 
            //此消彼长 
            //***
            v=e[i^1].v; 
        }
        nf+=mf[t];//汇入一股新的流量 
    }
    return nf; 
}
signed main(){
    cin>>n>>m;
    s=1,t=n;

    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w*10000+1);add(v,u,0);

    }

    int ans=EK();

    cout<<ans/10000<<' '<<ans%10000<<endl; 
}