周报

二分图最大匹配 & 最大流

引入

给出一个小写字母的子集,从这些字母的所有排列中选出 $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

发表评论