网络流总结

网络流，就是一张有向图中给每一边分配一个容量，流可以沿着有容量的边移动。对一个给定的网络，其一个可行流为从源点到汇点的一种流量方案。

网络流问题就是解决最大流、可行流、费用流等抽象问题的一种模型。对一个可行流来说，它有如下特性：

除了源汇点外，每一个点的入流与出流相等
经过每条边的流量不超过该边容量上限

则最大流就是到达汇点的流量最多的一个可行流，它也满足上述性质。

## 最大流

求最大流可以采用 Dinic、SAP、ISAP 等算法，但我们主要介绍 Dinic。Dinic 算法分为寻找分层图与增广两个部分。下面不加解释地放上 Dinic 的代码：

struct Dinic{
    struct Edge{int v,res;};
    vector<Edge> edg;
    vector<int> a[V];
    int st,ed;

    void AddEdge(int u,int v,int cap){
        edg.push_back((Edge){v,cap});
        edg.push_back((Edge){u,0});
        int siz=edg.size();
        a[u].push_back(siz-2);
        a[v].push_back(siz-1);
    }

    int dep[V];
    bool BFS(){
        memset(dep,-1,sizeof(dep));
        queue<int> q;
        q.push(st);dep[st]=0;

        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<a[u].size();i++){
                Edge e=edg[a[u][i]];
                if(dep[e.v]==-1&&e.res>0)
                    q.push(e.v),dep[e.v]=dep[u]+1;
            }
        }

        return dep[ed]!=-1;
    }

    int cur[V];
    int DFS(int u,int minF){
        if(u==ed||minF==0)return minF;

        int tmpF,sumF=0;
        for(int &i=cur[u];i<a[u].size();i++){
            Edge &e=edg[a[u][i]];
            if(dep[e.v]==dep[u]+1&&(tmpF=DFS(e.v,min(minF,e.res)))>0){
                e.res-=tmpF,edg[a[u][i]^1].res+=tmpF;
                sumF+=tmpF;minF-=tmpF;
            }
            if(minF==0)break;
        }

        return sumF;
    }

    int MaxFlow(){
        int ret=0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            ret+=DFS(st,INF);
        }
        return ret;
    }
};

上述代码用残量表示边的流量数据。对这份代码的解释很容易在网络上找到，在此不做赘述，而只点出实际写时的易错点：

寻找分层图时，不能经过残量为 0 的边。
利用当前弧结构保存时，每一次寻找增广路前要清零。并且寻找增广路时要使用引用来更新当前弧。
寻找增广路时要对当前边进行修改，因此要对边使用引用而不能单纯复制内容
对边的四个操作要保证修改的对象和数值是否正确
如果流量为 double 类型，需要 DCmp 判断是否为 0，而不能直接与 0 比较

这是一些很 naive 且很容易忘记的错误。放出以警示自己。

### 带上下界的流

带上界的流一般都采用拆点的方式建图来保证其上下界功能。考虑好必须经过的流量是哪些，可以经过的流量是哪些。

#### 带上下界可行流

##### 无源汇

对于 $E = (u , v) $，若其流量限定为 $ [low , upp]$，则我们可以先考虑特殊情况。

没有下界：普通的网络流，从 $u$ 向 $v$ 连容量为 $upp$ 的边。
没有上界：$u$ 节点必须输出 $low$ 流量，$v$ 节点必须流入 $low$ 流量。根据这个条件，可以考虑从 $u$ 向 $t$ 连流量为 $low$ 的边，从 $s$ 向 $v$ 连流量为 $low$ 的边，这样就满足了上述条件。

我们发现这两个不互相干扰，一起使用即可。明显，整个网络拥有一个可行流的等价条件是，新增的下界边都满流，否则没有可行流。

由于新网络入流与出流相等，而无源汇的网络满足流量平衡，因此 s 的出流等于 t 的入流，也就满足了新增加的边如果从 $s$ 得到了流量，则一定跑到了 $t$，而不会中途消失。此时 t 的最大流就是经过这些下界边的总流量。

##### 有源汇

从 $t$ 向 $s$ 连一条容量为 $\infty$ 的边，这样网络就变成无源汇的上下界，跑可行流即可。之所以需要变成无源汇而不能拆边后直接跑，是因为无源汇的网络做法考虑了流量平衡，而有源汇的网络明显源汇是不平衡的。如果不连 $(t , s) $的边，那么改建后原网络的 $s$ 根本就没有流量。这很明显不可行。

#### 有源汇带上下界最大流

##### 普通做法

我们的立足点是无源汇上下界可行流的求法，因此考虑把有源汇先转成无源汇。按照无源汇可行流的方法建图并跑最大流，得到的是一个原图的可行流，此时的下界应该是填满的（显然，不填满就连可行流都没有）。在残余网络上从原图的 $S$ 到 $T$ 跑最大流就是答案。（当然我不是很理解。）

##### 二分做法

我们仍转换为无源汇，但是设从 $T$ 到 $S$ 的边有下界 $x$，并跑无源汇可行流。明显，如果新图具有可行流，则说明原图能有 $x$ 的流量从 $S$ 到达 $T$，否则没有。这个性质可以二分。

#### 带上下界最小流

如果不带上下界，则最小流就是零流，没有什么好求的。

##### 普通做法

考虑转化为无源汇，但这次我们不连接从 $T$ 到 $S$ 的边，直接跑 $SuperS$ 到 $SuperT$ 的最大流。再加上从 $S$ 到 $T$ 的边，从 $SuperS$ 到 $SuperT$ 跑一次最大流。若从 $S'$ 出发的边满流，则 $( T , S )$ 的流量为最小流，反之无解。（当然我不是很理解。）

##### 二分做法

#### 总结

我们所有上下界流的基础都是建立在上下界无源汇可行流上，因此这个模型的转换是很重要的。另外，上下界最大 / 最小流的二分解法虽然比普通解法多出一个 $\log$，但是却很容易理解。实际运用上应该是足够的。

## 最小割

流网络 $ G = (V , E) $的割（Cut）$ [ S , T ] $将点集 $ V $划分为 $ S $和 $ T ( T = V − S )$两个部分，使得源 $ s ∈ S $且汇 $t ∈ T $。符号 $ [ S , T ] $代表一个边集合 $ { u , v | u , v ∈ E , u ∈ S , v ∈ T } $。割 $ [ S , T ] $的容量（Capacity）定义为 $ c ( S , T ) $，一般记为 $ c [S , T] $。一个网络的最小割也就是该网络中容量最小的割。（定义来自《最小割模型在信息学竞赛中的应用》胡伯涛）

注意边集中方向为 $T\to S$ 的边的容量不计算在割集内。即最小割的容量只为顺着 $S\to T$ 到达的边的容量和。

最小割拥有一些不错的性质：

最小割将点集分割成两个部分，且最小割只包含了两端点属于不同点集的边的容量
最大流最小割定理：一个网络中的最大流等于最小割

第二个性质很重要，它给了我们一个求最小割的方法。而第一个性质给了我们一个转换模型的思路。我们给出如下性质：

最小割一定是最大流中的满流边，但满流边不一定是最小割中的边

这个性质的反例可以在论文中找到。因此寻找最小割边时，需要从源点 DFS 顺着有残量的边遍历，则两端点只被遍历一个的边为最小割边。注意这个有残量的边包括网络中的反边，有些点可能能从反边被到达，因此需要 DFS 而不能单独认为满流边就是最小割边。

### 平面图最小割

可以参考论文《两极相通 —— 浅析最大 — 最小定理在信息学竞赛中的应用》周冬。

平面图的对偶图：把平面图的面当点，连接两个面的边当两个点的边的图。平面图有不错的性质：

欧拉公式：顶点数 $ + $面数 $ - $边数 $ = 2$
平面图的对偶图也是一个平面图

对一个源汇点都在无界面的边界的网络，如何根据平面图求它的最小割？我们从 $S$ 到 $T$ 连接新边创建出附加面，并对这个图创建对偶图，其中 $S'$ 和 $T'$ 为对偶图在附加面与无界面的点。则我们画个图就能发现，$S' $到 $ T'$ 的一条路径就是原图的一个割。因此原图的最小割相当于新图的最短路径。

我们得到一个感受：当原问题不好入手时，考虑它的对偶问题。

### 最大权闭合图

这类题目是求具有依赖关系的最大权子图：选择 A 会有一定权值，但同时要选择 B 和 C，它们也会产生权值，这样的关系构成一张有向图。选择有向图的一个子图，使得若 $v$ 在点集，则 $v$ 的出边指向的点也在点集。

对这类题目的详解在论文有。此处只阐明算法：

对原图的所有边容量赋为 $\infty$
从 $S$ 向正权点连权值为 $w$ 的边
从负权点向 $T$ 链权值为 $-w$ 的边
最大权闭合子图 = 正权点权和 - 新图最小割

## 二分图最大匹配

二分图本身就有一个两端属于不同点集的边集，因此二分图常常被询问最大匹配。最大匹配即，选定一个边集，使得边集中的所有点不相交。二分图的最大匹配有 $\mathrm{O}(nm)$ 的匈牙利算法（Hungarian Algorithm），非二分图的最大匹配需要带花树算法（Blossom Algorithm）。

不加注释地给出匈牙利算法代码：

bool vst[N];int lnk[N];
bool DFS(int u){
    for(int v=1;v<=nV;v++)
        if(g[u][v]&&!vst[v]){
            vst[v]=1;
            if(!lnk[v]||DFS(lnk[v])){
                lnk[v]=u;
                return 1;
            }
        }

    return 0;
}

int ans=0;
for(int i=1;i<=nV;i++){
    memset(vst,0,sizeof(vst));
    if(DFS(i))ans++;
}

这个算法给出的是邻接矩阵做法，我们可以很轻易地改为邻接表。需要注意的点：

每次开始搜索前，清空访问数组
只有没有访问的节点可以操作

## 图的性质

明确以下概念：

点相关
- 最小点覆盖
- 最大独立集
- 最小点权覆盖
- 最大点权独立集
边相关
- 最小边覆盖
- 最大匹配

这些概念都可以在论文中找到具体定义，但我们重点讨论它们的性质：

最大匹配数 $+$ 最小边覆盖数 $=$ 顶点数（条件：联通图）
最大独立集 $+$ 最小点覆盖数 $=$ 顶点数
König 定理：最大匹配数 $=$ 最小点覆盖（条件：二分图）
最大流 $=$ 最小割
最小割 $=$ 最小点权覆盖集（条件：二分图）
最小点权覆盖集数 $+$ 最大点权独立集数 $=$ 顶点数（条件：二分图）

大部分性质都可以概括为：最值 $ = $最值，最小 $ + $最大 $ = $ 顶点数。后三条可以得到一个计算最大点权独立集的有效算法。具体的讨论和证明可以参考《两极相通 —— 浅析最大 — 最小定理在信息学竞赛中的应用》周冬。

## 最小费用最大流

给网络中的每一个边一条边权，求使得最大流的情况下的最小费用。下面不加注释地给出代码：

struct Dinic{
    struct Edge{int v,w,res;};
    vector<Edge> edg;
    vector<int> a[V];
    int st,ed;

void AddEdge(int u,int v,int w,int cap){
    edg.push_back((Edge){v,w,cap});
    edg.push_back((Edge){u,-w,0});
    int siz=edg.size();
    a[u].push_back(siz-2);
    a[v].push_back(siz-1);
}

int dis[V],pa[V],det[V];
bool SPFA(){
    static int inQ[V];
    memset(inQ,0,sizeof(inQ));
    memset(dis,0x3f,sizeof(dis));
    deque<int> q;q.push_back(st);
    dis[st]=0,inQ[st]=1,det[st]=INF,pa[st]=-1;

    while(!q.empty()){
        int u=q.front();q.pop_front();inQ[u]=0;
        for(int i=0;i<a[u].size();i++){
            Edge &e=edg[a[u][i]];
            if(e.res>0&&dis[e.v]>dis[u]+e.w){
                dis[e.v]=dis[u]+e.w;
                det[e.v]=min(det[u],e.res);
                pa[e.v]=a[u][i];
                if(!inQ[e.v]){
                    if(!q.empty()&&dis[q.front()]>=dis[e.v])q.push_front(e.v);
                    else q.push_back(e.v);
                    inQ[e.v]=1;
                }
            }
        }
    }

    return dis[ed]!=INF;
}

void Augment(int &w){
    w+=dis[ed]*det[ed];
    int u=ed;
    while(u!=st){
        edg[pa[u]].res-=det[ed];
        edg[pa[u]^1].res+=det[ed];
        u=edg[pa[u]^1].v;
    }
}

int MaxFlowMinCost(){
    int ret=0;
    while(SPFA())Augment(ret);
    return ret;
}

要点：

增广过程与 SPFA 相似，但仍要注意只有有残量的边可以通过。
SPFA 过程注意是否出队入队，是否取消标记，是否入对位置正确。

### 费用流拆边

一条边所花费的费用是随流量线性增长。如果呈二次增长，甚至三次增长呢？需要拆边。

假设 $f $为流量，$cap $为边容量，$w = f ^ 2 $为费用，则当 $ f = 1 $时 $ w = 1 $，$ f = 2 $时 $ w = 4$，$ f = 3 $时 $ w = 9 $。我们把边拆为 $ cap $ 条，每条容量是 $1$，费用分别是 $1,3,5,\dots$ 则不难发现在流量相同时，费用会选择最小的 $ f $条，而这 $ f $条的费用加起来刚好为 $ w= f ^ 2$。当流量呈更复杂的多项式时，可以利用导数将边拆分。但很明显拆边有前提：流量必须是整数，多项式导数必须递增。

### 带权二分图匹配

如果有权，则可以给边赋权用费用流求解匹配。从 $S$ 向 $X$ 集合、从 $Y$ 集合向 $T$ 连权值为点权、容量为 $1$ 的边，跑最大流最小费用即可。

## 练习

### 最大流

####USACO4.2.1 草地排水

最大流模板题目。

####BSOJ1721 上下界可行流 & BSOJ1723 上下界最大流 & BSOJ1725 上下界最小流

上下界网络流的练习题。

####BSOJ2547 网络流 24 题 - 6 最长递增子序列

第二问可以考虑每个点只能被选一次，并且假设当前节点结尾的 LIS 为 $ d $，则当前节点只能向后面 LIS 为 $ d + 1 $ 的节点（否则不是 LIS）连容量为 $1$ 的边。最后 $ S $连 $ d $ 为 $1$ 的点，$ d $为全局 LIS 的点向 $T$连，跑最大流即可。第三问只需要修改部分点流量为 $$。

####SDOI2015 星际战争

二分答案判断最大流是否足够。注意精度。

### 二分图最大匹配

####SCOI2015 小凸玩矩阵

二分答案 $ans$，$X$ 集合为行，$Y$ 集合为列，选中一个元素等于匹配两个点，每次只能选择小于等于 $ans$ 的元素。判断这些元素（匹配）是否有 $ (n - k + 1) $个。注意第 $k$大而不是第 $k$ 小。

####USACO2005NovGold Asteroids

有行星的位置连接一条边，求最小点覆盖。可转化为最大匹配。

####USACO2005JanGold 泥泞的牧场

注意到每个点只能被横行或纵列覆盖（可以同时覆盖）。对于连续的泥泞，我们一块木板盖上是最好的。因此我们可以把图分块。横向的分块与纵向的分块编号后，一个泥泞就只能对应一条横向与一条纵向分块的交点了。

题目相当于转化为选择尽量少的分块，使得每个交点都被覆盖。如果把分块变成左右两端的点，交点变为它们之间的边，则原题目化为最小点覆盖。为什么可以转化？我们发现两个块要么有交点，要么没交点，并且只有横向块与纵向块相交，这完全符合二分图性质。

####BSOJ1775 xinyue 的约会

同上，但需要考虑有些边不需要添加。

####BSOJ2569 网络流 24 题 - 3 最小路径覆盖

把每个点拆成入点和出点，这样一个匹配就是一个边。在匹配中，每一个点的前驱和后继是唯一的，而只有起点不存在前驱，终点不存在后继。有多少个点没有前驱或后继，就有多少条路径。因此对于一个匹配，其路径数 = 点数 - 匹配数。

因此，最少路径 = 点数 - 最大匹配。

有关路径的问题可以将其拆成二分图，再观察路径的性质。

### 最小割

最小割的题目算是比较有价值，也是比较难转换的模型题目。

####POJ2125 Destroying the Graph

每条边可以被入点破坏也可以被出点破坏。因此构造二分图求最小割。

####POJ3469 Dual Core CPU

考虑没有额外代价的情况，则一个任务只能在两个 CPU 的其中一台运行。这个就是最小割模型，$S $向任务 $ i $连边权为 $ a_i$的边，$i $向 $ T $连边权为 $ b_i$的边，则最小割就把所有点集分成两个部分（要么属于 $ S $，要么属于 $ T $），且使得所有割边代价最小。

考虑加上代价。我们希望当 $ a $与 $ b $不在同一个点集时能有额外的权 $ w _i$，这很像最小割的定义，因此我们考虑把 $w_i$也加入到最小割。具体做法是在 $ a $与 $ b $之间连边权为 $ w_i$的无向边，这样当 $ a $与 $ b $ 在同一个集合时此边不会是割边，而不在同一个集合时，会把额外代价计算。这就解决了问题。

往往要从定义出发：割边是连接两个属于不同集合的点的边集。下面的题目也显示出这个特点。

####SPOJ839 Optimal Marks

我们发现因为存在位运算，所有边权的总和最小等价于边权的每一位总和最小。因此单独考虑每一位，且每一位都只有 $ 0$ 和 $1 $ 可以取。注意到 xor 的定义是两个数不同则为 $1$，相同为 $0$，边权只有端点的两个数不同时才被计算，这和最小割的定义同样很像。

因此最小割模型显然。把两个集合当成选择的值，向每个点连接容量为 $\infty$ 的边，有边相连的两个点连容量为 $ 1 $的边。这么做的目的是：割边只能在 ** 特定的边 ** 取到，而不能在 ** 容量为 **$$ 的边取到。对每一位跑一次最小割即可。

我们得到一个直观的感受：如果一条边不想成为割边，只需要把容量设为 $\infty$ 。

####ZJU2676 Network Wars

见论文。此处重点讨论细节。

对给定网络，我们需要选出一个最小割集。由于分数规划使得边权可能为负，而负边权相当于反边，是不会被计算在最小割的容量的，因此需要手动叠加，而只对边权 $ > 0 $ 的边求割。

####BSOJ2550 网络流 24 题 - 9 方格取数问题

对棋盘黑白染色后发现相邻的不同颜色点之间只能选择其中一个。因此把有冲突的点连边，求最大独立集（权为 $1$ 的最大点权独立集）即可。注意是二分图，转化求最小点权覆盖集 $\to$ 最小割 $\to$ 最大流。

####CQOI2017 老 C 的方块

题目描述很复杂，大致就是在一个特殊的网格上不能有特定图形出现，而去除一个网格需要一定费用。

然后我们观察四个图，发现特殊边两侧刚好连接两个格子。“某些状态不能共存，而去掉某个状态需要一定代价” 的想法让我们想到最小割（虽然数据范围上不是这样的）。因此有这些形状的格子要连接起来，并且至少有一个连接源点或汇点。经过一番构图，我们构造出下面这种网络：

\[ \begin {matrix} \vdots & &\vdots & &\vdots & &\vdots & &\vdots & &\vdots\\ \downarrow &\Leftarrow &\leftarrow &\leftarrow &S & &T &\leftarrow &\leftarrow &\Leftarrow &\leftarrow &\cdots\\ \downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow &\\ T & &S &\rightarrow &\rightarrow &\Rightarrow &\rightarrow &\rightarrow &T & &S &\cdots\\ \uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow &\\ \uparrow &\Leftarrow &\leftarrow &\leftarrow &S & &T &\leftarrow &\leftarrow &\Leftarrow &\leftarrow &\cdots\\ \downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow &\\ T & &S &\rightarrow &\rightarrow &\Rightarrow &\rightarrow &\rightarrow &T & &S &\cdots\\ \uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow &\\ \uparrow &\Leftarrow &\leftarrow &\leftarrow &S & &T &\leftarrow &\leftarrow &\Leftarrow &\leftarrow &\cdots \end {matrix} \\ \text {（有没有想到洋流图）} \]

每个交点是原图中的一个方块，双线箭头代表图中的特殊边。我们在这张网络图上能发现原图中的四种方块都对应一条从 $S$ 到 $T$ 的边，我们只需要求最小割就是最小花费。问题是怎么设置边权。

明显处于 $S$ 和 $T$ 上的点应该各自连 $w$ 到 $S$ 或 $T$，那特殊边两侧的两个方块呢？如果要删掉一个方块，则只需要删掉一个就好了，两个同时删是不划算的。因此我们只需要给特殊边设两个方块的较小 $w$ 即可。

虽然本题点的规模达到了 $10^5$，但棋盘很大，连边只在相邻的方块出现，因此边数不大。跑跑最大流就过了。

是道建图好题。我们可以得到一个直观感受：最小割可以解决不共存的最小代价问题。这跟上面利用割的定义最小化分点代价不同，其出发点是源汇点的联通性。

### 最大权闭合图

####BSOJ2543 网络流 24 题 - 2 太空飞行计划

很明显的最大权闭合图模型，直接转化。

####NOI2006 最大获利

见论文。选定一个边同时要选定两个点，转化模型。

####TJOI2015 线性代数

转化题目后发现相当于有许多物品，要得到物品 $ i $和 $ j $需要先选定 $ i $和 $ j$，而选定 $ i $和 $ j$ 都需要代价。接着就可以做了。

有个神奇的做法是暴力寻找不要什么物品，时间复杂度 $ (n ^ 3 n)$，跑起来还挺快。

### 费用流

####BSOJ4914 疯狂的方格取数

拆点。由于网络流与边有关，因此和点有关的题目往往需要把点拆掉来建立边。

####ZJOI2010 网络扩容

第一个最大流很简单。

第二个我一开始估计是在残余网络上操作，然后跑个 DP 计算每条路径扩展 k 所需要的费用，再统计和即可。不过这不好实现还容易 TLE。发现所需费用是费用流的表达式，但是如果直接跑费用流，我们希望有容量的边不计算权值，没流量的边计算权值，怎么办？

残余网络中，原图都加一条边权为 $w$，容量为 $\infty$ 的边。再从超级源点 $s$ 向 $1$ 建边权为 $0$，容量为 $det$ 的边。这样，在跑费用流的时候，如果一个边有流量就会优先选择这条没有花费的边，否则只能选择有花费的新边。

这个思路挺巧妙的，虽然我觉得对 $n=1000,m=5000$ 的数据跑 $\mathrm{O}(n^2m)$ 有点夸张。不过据说 Dinic 的复杂度和 SPFA 一样是个迷，因此还是可以跑的。

####SCOI2007 修车

本质上是一个打水问题，不过在不同的维修队列里花费时间也不一样。

费用流模型不难想到，可是具有后效性。然而我们发现把每个维修人员的

【未完成】

####NOI2008 志愿者招募

题目太神，不会做。但是还是放上 BYV 的题解。

具体的思路是把不等式添加变量修改为等式，这样容易思考。其次发现每个人都从某段时间开始，某段时间结束，可以考虑到差分。两者结合就得到了新的等式，并且由于差分的特性，每个有关变量都刚好出现两次且符号相反。

啧啧称奇。（虽然我不知道为什么推出来之后，需要求最大流。）

## 总结

网络流通常用来求一类有限制（选择次数、不可同选）的题目。建模相比起算法往往更重要，因此如何构造网络是网络流题目的一个重点。

需要掌握图的点与边集关系，尤其是二分图
- 最大匹配数 $+$ 最小边覆盖数 $=$ 顶点数（条件：联通图）
- 最大独立集 $+$ 最小点覆盖数 $=$ 顶点数
- König 定理：最大匹配数 $=$ 最小点覆盖（条件：二分图）
- 最大流 $=$ 最小割
- 最小割 $=$ 最小点权覆盖集（条件：二分图）
- 最小点权覆盖集数 $+$ 最大点权独立集数 $=$ 顶点数（条件：二分图）
网络流的建模入手点
- 有关选择的依赖关系的问题，可以考虑最大权闭合图
- 有关路径的问题可以按照出边入边将其拆成二分图，再观察路径的性质
- 有关等式或不等式，考虑流量平衡（如上下界网络流、志愿者招募）
- 有关不共存的最小代价，考虑最小割使源汇不联通的性质，在不共存状态间连边，再与源汇连边求最小割