二分图最大匹配

匈牙利算法

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, k;

int tot, head[N];
struct Edge {
    int nex, to;
}e[N * N];
void add(int a,int b) {
    e[++tot] = {head[a], b};
    head[a] = tot;
}

int dfn[N], tim;
int combine[N];
int dfs(int u, int tim) {
    for (int i = head[u]; i; i = e[i].nex) {
        int to = e[i].to;
        if (dfn[to] == tim) continue;
        dfn[to] = tim;
        if (!combine[to] || dfs(combine[to], tim)) {
            combine[to] = u;
            return 1;
        }
    }
    return 0;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, a, b; i <= k; i++) {
        scanf("%d%d", &a, &b);
        if (a >= 1 && a <= n && b >= 1 && b <= m) {
            add(a,b);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dfs(i, ++tim)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

网络流算法

void init() {
    scanf("%d%d%d", &n, &m, &e);
    S = n + m + 1; T = S + 1;
    N = n + m + 2;
    dinic.init(N, S, T);
    for (int i = 1, a, b; i <= e; i++) {
        scanf("%d%d", &a, &b);
        if (a >= 1 && a <= n && b >= 1 && b <= m) add(a, b + n, 1);
    }
    for (int i = 1; i <= n; i++) add(S, i, 1);
    for (int i = 1; i <= m; i++) add(n + i, T, 1);
}

二分图相关定理

最小点覆盖

定义：最小点覆盖，即求最少的点，使得每条边都至少和其中的一个点相关联。

定理：二分图最小点覆盖等于最大匹配。

构造：我们 \text{dfs} 左边所有未匹配的点，每次 \text{dfs} 从左往右只走未匹配边，从右往左则只走匹配边；二分图的一种最小点覆盖就是左侧的未访问点加上右侧的已访问点。

例题：hdu6808 Go Running（2020hdu多校第四场1007）

题目大意：

在一条双向的轴上，有若干同学在跑步，每位同学的速度是固定的 1 单位长度/s。在 n 个时刻 t，位置 x 上将至少有一个人在跑步，但是方向不确定，仅能确定有人。问能确定最少有多少同学在跑步？

分析

转化成平面图，x 轴为时间轴，y 轴为跑步的轴，则每个同学有一个起点，在一条斜率为 1 或 -1 的直线上运动。问题转化为，我们最少能用多少条斜率为 1 或 -1 的直线覆盖全部的点。

由于斜线不好处理，我们考虑将坐标轴顺时针旋转 45 度。(x,y) 的坐标被映射到 (x + y, x – y)。问题转化为在直角坐标系中，最少用多少条平行于 x 轴或者平行于 y 轴的直线覆盖全部点。

将每条平行与 x 轴的线看成二分图左边的点，平行于 y 轴的线看成二分图右边的点；原图中的每个点，就对应二分图中的一条边。问题边转化为了二分图的最小点覆盖（选取最少的点，使得每条边均有至少一个点被选中）。由相关定理，二分图的最小点覆盖等于其最大匹配。跑 Dinic 即可。

int n;
int x[N], y[N], a[N], b[N];

int main()
{
    int ; scanf("%d", &);
    while ($--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x[i], &y[i]);
            a[i] = x[i] + y[i];
            b[i] = x[i] - y[i];
        }
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n);
        int ta = (int)(unique(a + 1, a + 1 + n) - a - 1);
        int tb = (int)(unique(b + 1, b + 1 + n) - b - 1);
        int S = ta + tb + 1, T = S + 1;
        dinic.init(T, S, T);
        for (int i = 1; i <= n; i++) {
            int idx = (int)(lower_bound(a + 1, a + 1 + ta, x[i] + y[i]) - a);
            int idy = (int)(lower_bound(b + 1, b + 1 + tb, x[i] - y[i]) - b);
            add(idx, idy + ta, 1);
        }
        for (int i = 1; i <= ta; i++) {
            add(S, i, 1);
        }
        for (int i = 1; i <= tb; i++) {
            add(i + ta, T, 1);
        }
        printf("%lld\n", dinic.Dinic());
    }
    return 0;
}

最大独立集

定义：从无向图的 V 个顶点中选出 k 个点，使得这 k 个点互不相邻，那么最大的 k 就是这个图的最大独立集；

二分图的最大独立集 = 最小链覆盖

定理：二分图最大独立集 = |V|- 最小点覆盖

例题：P2765 魔术球问题

题目大意：

假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,\cdots 的球。要求：每次只能在某根柱子的最上面放球；同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在 n 根柱子上最多能放多少个球。例如，在 4 根柱子上最多可放 11 个球。

分析：

将所有数依次加入，若 a+b 为完全平方数且 a<b 则连一条 a 到 b 的边。问题就转化为，最小链覆盖的数量是否小于等于 n。用网络流跑二分图，每次加入新的点后，在残量网络上跑即可。
输出方案的时候，记录下每条链的起始，往下走即可。

int squ[105];
void init() {
    for (int i = 1; i <= 100; i++) squ[i] = i * i;
    add(S, 1, 1); add(S, 2, 1);
    add(1 + N, T, 1); add(2 + N, T, 1);
}

void solve(int u, vector<int> &ans) {
    for (int i = head[u]; i; i = e[i].nex) {
        int to = e[i].to;
        if (to == S || to == T || e[i].w) continue;
        ans.push_back(to - N);
        solve(to - N, ans);
    }
}

int main() {
    scanf("%d", &n);
    vector<int> start(n + 1); start[1] = 1; start[2] = 2;
    dinic.init((N << 1) - 10, S, T);
    init();
    for (num = 3, sum = 1; ; num++) {
        add(S, num, 1);
        add(num + N, T, 1);
        for (int i = 2; squ[i] - num < num; i++) {
            if (squ[i] - num <= 0) continue;
            add(squ[i] - num, num + N, 1);
        }
        int update = dinic.Dinic();
        maxflow += update;
        sum = num - maxflow;
        if (sum > n) break;
        if (!update) start[sum] = num;
    }
    printf("%d\n", --num);

    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        ans.resize(0); ans.push_back(start[i]);
        solve(start[i], ans);
        for (size_t x = 0; x < ans.size(); x++) {
            printf("%d%c", ans[x], x == ans.size() - 1 ? '\n' : ' ');
        }
    }
    return 0;
}

Dilworth 引理

几个定义：

偏序集：一个偏序集 S 中，设 x\in S,y\in S，则 x\le y 或 x \ge y（此时 x,y 可比），或者 x,y 不可比。

链：一个偏序集 S 的全序子集（所谓全序是指任意两个元素可比较）。

反链：一个偏序集 S 的子集，其中任意两个元素不可比较。

定理内容：

对偏序集 < S,\le >，设A中最长链的长度是 n，则将 S 中元素分成不相交的反链，反链个数至少是 n。

由定理，偏序集的 最长反链 = 最小全序集覆盖。

例子：P1020导弹拦截

题目大意：导弹拦截系统可以拦截掉一个高度为不下降子序列的所有导弹。问需要多少个导弹拦截系统？

分析：全序集为 < S,\ge >，最小全序集覆盖等于最长反链，即全序集 < S,< >。因此求出最长上升子序列即可。

在 DAG 与二分图中的应用

1. 有向无环图最小不相交路径覆盖
   把原图中的每个点 V 拆成 V_x 和 V_y，如果有一条有向边 A−>B，那么就加边 (A_x,B_y)。这样就得到了一个二分图，最小路径覆盖=原图的节点数-新图最大匹配。

2. 有向无环图最小可相交路径覆盖
   先用 floyd 求出原图的传递闭包，即如果 a 到 b 有路，那么就加边 (a,b)。然后就转化成了最小不相交路径覆盖问题。

例题：P4298 [CTSC2008]祭祀

题目大意：

给一个有向无环图：
1）找出最多的点，使得这些点之间互相不可达。
2）输出其中一种方案。
3）在保证找出的点最多时，找出哪些点可能被选。

分析：

1）设偏序集 S：<V, 可达>。则题中要求的是最长反链。我们先用 Floyd 传递闭包，得到可达矩阵，构造一个新图，我们要求的即为此图中的最小不相交路径覆盖。

2）我们要求的是原图中的最大独立集，等价于求其拆点后二分图的最大独立集（每组点同时被选/同时不选）。由二分图相关定理，最大独立集为最小点覆盖的补集。我们只需求出二分图的最小点覆盖即可。

3）如果一个点是可选的，我们先假设选了它。于是一切可到达它的、它可到达的点均无法被选择。将这些点 ban 掉，剩下的点所构成的最大独立集应当为初始答案减一。

#include <bits/stdc++.h>
using namespace std;
const int N = 105;

int n, m;
bitset<N> l[N];
void Floyd() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (l[j][i]) {
                l[j] |= l[i];
            }
        }
    }
}

int head[N * 2], tot;
struct Edge {
    int nex, to;
}e[N * N * 2];
void add(int a, int b) {
    e[++tot] = {head[a], b};
    head[a] = tot;
}

int dfn[N], tim;
int combine[N];
int ban[N];
int dfs1(int u, int tim) {
    if (ban[u]) return 0;
    for (int i = head[u]; i; i = e[i].nex) {
        int to = e[i].to;
        if (dfn[to] == tim || ban[to]) continue;
        dfn[to] = tim;
        if (!combine[to] || dfs1(combine[to], tim)) {
            combine[to] = u;
            return 1;
        }
    }
    return 0;
}


int xvis[N], flg[2][N];
void dfs2(int u) {
    flg[1][u] = 1;
    for (int y = 1; y <= n; y++) {
        if (l[u][y] && combine[y] != u && !flg[0][y]) {
            flg[0][y] = 1;
            if (combine[y]) dfs2(combine[y]);
        }
    }
}

int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        l[a][b] = 1;
    }
    Floyd();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (l[i][j]) add(i, j);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dfs1(i, ++tim)) ans++;
    }
    printf("%d\n", n - ans);

    for (int i = 1; i <= n; i++) {
        if (combine[i]) xvis[combine[i]] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (!xvis[i]) dfs2(i);
    }
    for (int i = 1; i <= n; i++) {
        if (!flg[1][i] || flg[0][i]) putchar('0');
        else putchar('1');
    }
    puts("");

    for (int x = 1; x <= n; x++) {
        tim = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(combine, 0, sizeof(combine));
        memset(ban, 0, sizeof(ban));
        int now = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (i == x || l[i][x] || l[x][i]) {
                cnt++; ban[i] = 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (dfs1(i, ++tim)) now++;
        }
        if (n - cnt - now == n - ans - 1) putchar('1');
        else putchar('0');
    }
    puts("");
    return 0;
}