周报

二分图最大匹配 & 最大流

2020年4月5日

引入

给出一个小写字母的子集，从这些字母的所有排列中选出 $N$ 个构成集合 $W$。现从中取出一个最大的子集，使得这个子集中的任意两个单词 $x,y$，满足不能通过交换 $x$ 中一对字母得到 $y$。问这个最大子集的大小。

二分图构造

如果 $x$ 可以通过交换一对字母得到 $y$，我们就连一条边 $(x,y)$，最终答案就是构造出的图的最大点独立集。特别的，此题中构造的图必定是二分图。

原因在于每个单词中，一个字母最多出现一次。考虑某个位置 $p$ 的字母 $c$，$c$ 离开 $p$ 必定对应一次 $c$ 回到 $p$，对每个位置这么考虑，最后交换次数必定是偶数。

由于「最大点独立集＋最小点覆盖＝顶点个数」，「最小点覆盖＝最大匹配」，问题转化为求解二分图的最大匹配。可以利用匈牙利算法求解。

匈牙利算法

匈牙利算法核心思想是，不断从图中寻找增广路，每次找到增广路就可以使得匹配加一。

这里的增广路是指，从一个没有匹配的点出发，沿着非匹配边、匹配边、非匹配边……最终经一条非匹配边到达一个非匹配点的路径。

例子
二分图

1，2 分别直接和 4，5 匹配，然后 3 尝试和 4 匹配。

然而 4 已经和 1 匹配 $\to$ 1 能否和其他点匹配？ $\to $ 1 尝试和 5 匹配 $\to$ 2 能否和其他点匹配？$\to$ 2 和 6 匹配 $\to$ 1 和 5 匹配 $\to$ 4 和 1 匹配。

这个过程中 $1\to4、2\to5、3\to4\to1\to5\to2\to6$ 都是增广路。

（伪）代码描述
match[1...n] = [NULL]        //匹配的点
ans = 0

for all u in V
    path[1...n] = [false]    //点是否在这次搜索的增广路上
    if augmentation(u)
        ++ans


bool augmentation(u)
    for all v:(u,v) in E
        if path[v] == false
            path[v] = true
            if match[v] == NULL || augmentation(v)
                match[u] = v
                match[v] = u
                return true
    return false

复杂度 $O(VE)$。

一些细节

  • 如果可能，没有必要对每个点尝试增广，只需要遍历二分图的一个点集即可。
  • 标记一个点是否在增广路上，可以使用时间戳。具体来说，每次第 6 行搜索前标记一下这是第几次搜索，检查一个点是否在增广路上，只需要检查这个点的时间戳是否是这次搜索的时间。

最大流

二分图最大匹配还可以转化为最大流问题。

在原二分图的基础上，令原图的边的容量为无穷大，同时令二分图一个点集中的所有点与源点相连，边的容量为 1，另一个点集都与汇点相连，边容量也为1。那么这个网络的最大流等于最大匹配。

每单位流量对应两个点集中的各一个点。由于在原图基础上新构造的边容量为 1，所以其他流量均与这两个点无关，则它们之间的边即匹配中的一个元素。

求解最大流主要两个系列的算法：

  • 增广路。（EK、Dinic、ISAP）
  • 预流推进。

比赛中 Dinic 较实用。

EK (Edmond-Karp) 算法

不断寻找从源点 BFS，搜索到汇点的仍可以增大流量路径，暴力增广。

但是这样贪心并不一定可以得到最大流。

image-20200402211631514

如图，$S=1，T=6$，若一开始选择 $1\to2\to4\to6$，之后无法增广，但这并不是最优解。

为了解决这个问题，引入反向弧。为每次增广提供一个撤销选项。具体来说，反向弧初始容量为 0，若一条边容量减少一些，就同时向相反方向增加一些容量。感觉上反向弧相当于回溯。

复杂度 $O(VE^2)$。

Dinic 算法

Dinic 算法是 EK 算法的一个改进。相比 EK，Dinic BFS 过程中对原图进行分层，然后依靠 DFS 进行多路增广。

算法描述并不复杂：

while 可以从残量网络建立分层图
    使用 BFS 建立分层图
    while 分层图中有增广路
        增广，更新答案

Dinic 通常还会加入 『当前弧优化』。原理在于，对于某次 BFS 建立的层次图，某条边不会被多次增广。可以记录一个点有哪些边已经增广过了，下次 DFS 增广跳过增广过的边。

蓝书上的板子
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100 + 10;
const int INF = 1000000000;

struct Edge {
    int from, to, cap, flow;
};

struct Dinic {
    int n, m, s, t;
    vector<Edge> edges;   // 边数的两倍
    vector<int> G[maxn];  // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
    bool vis[maxn];       // BFS使用
    int d[maxn];          // 从起点到i的距离
    int cur[maxn];        // 当前弧指针

    void ClearAll(int n) {
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }

    void ClearFlow() {
        for (int i = 0; i < edges.size(); i++) edges[i].flow = 0;
    }

    void AddEdge(int from, int to, int cap) {
        edges.push_back((Edge){from, to, cap, 0});
        edges.push_back((Edge){to, from, 0, 0});
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        vis[s] = 1;
        d[s] = 0;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); i++) {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a) {
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++) {
            Edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] &&
                (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s, int t) {
        this->s = s;
        this->t = t;
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, INF);
        }
        return flow;
    }
};

挖坑+推荐，xht37’s blog

Views: 562

发表评论