二分图

若一无向图G, 可以将所有的点分成2个点集, 且2个点集内部没有连边, 那么称G可以划分为一张二分图

注意:

二分图的划分不一定唯一, 且不一定连通

有向图在实际问题中也可以划分二分图

存在二分图的充要条件 : 没有奇环 (总点数为奇数的环)

二分图的判定

染色法:任意选择没有访问的点开始dfs, 并且01交替染色只要出现一条边的2个断点相同, 那么就不是二分图

模板题

时间复杂度 $O(N+M)$

bool dfs(int u, int c) // 当前节点和当前节点的颜色
{
    color[u] = c; // 标记颜色

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (!color[j]) // 如果没有标记过颜色尝试标记
        {
            if (!dfs(j, 3 - c)) return false;
            // 出现冲突不存在二分图
            // 采用3 - c来翻转颜色
            // 1 -> 3-1 -> 2
            // 2 -> 3-2 -> 1
        }
        else if (color[j] == c)
            return false; // 当前出现冲突, 存在偶数环，不存在二分图
    }

    return true;
}

P1525 [NOIP2010 提高组] 关押罪犯

目标: 将同一座监狱中最大的怨气值最小化

1. 二分答案怨气值;

2. 设二分答案为x, 那么x及一下的怨气值是可以关在同一座监狱的, 比x大的必须分开;

3. 将x之上的权值连边, 建图后跑二分图判定, 若是二分图, 说明大于x的罪犯对可以分开;

4. 此题中连边表示两个罪犯相互排斥

Guard Towers

把曼哈顿距离看作怨气值，就比上一道题多了个快速幂

二分图的最大匹配

对于一张无向图G, 且G可以划分为二分图, 我们将一条边成为一组“匹配”, 在G中选出最多的匹配且所有选出的边不共点, 那么这一组边集, 就是一组G的最大匹配

匈牙利算法(求增广路径的一种方法)

增广路径:从左部未访问的点x到达右部未访问的点y

时间复杂度 $O(N^3)$

每次选择1号点集的一个点, 尝试与2号点集匹配 find(x)

find函数:

依次选择与当前节点所连接的点j

标记j遍历过

分两种情况看是否能匹配

1. match[j] == 0, j没有匹配过;

2. 已经匹配过了, 查看是否可以然与j匹配过的点还一个节点匹配

例子：

模板题 P3386

#include <bits/stdc++.h>
using namespace std;

const int N = 510, M = 5e4 + 10;
int h[N], e[M], ne[M], idx;
bool st[N]; // 表示1号点集的点x是否访问
int match[N]; // 表示2号点集的点x与谁匹配

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool find(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i]; // 与之连接的2号点集节点

        if (!st[j]) // 发现没有遍历过
        {
            st[j] = true; // 标记

            // 两种情况
            // 第一种情况 当前节点可以和j匹配
            // 第二种情况 j已经被选了, 查看与j匹配的节点是否能和2号点集的其他节点匹配
            if (!match[j] || find(match[j]))
            {
                // 可以匹配
                match[j] = u;
                return true;
            }
        }
    }

    // 没有一个2号点集的节点能与u进行匹配
    // 所有与之连接的节点都被选，且选那些节点的点没有一个可以让出节点
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    

    int n, m, e;
    cin >> n >> m >> e;

    memset(h, -1, sizeof h);

    int a, b;
    while (e--)
    {
        cin >> a >> b;

        add(a, b);
        // 建有向边，题目保证是一条从1号点集到2号点集的路径
    }

    int cnt = 0; // 记最大匹配数
    for (int i = 1; i <= n; i++)
    {
        memset(st, 0, sizeof st); // 每次清空遍历数组

        if (find(i)) cnt++; // 判断i能不能在不冲突的情况下与2号点集的节点匹配
    }

    cout << cnt;


    return 0;
}

P10937 車的放置

1. 考虑到每行每列只能放一个车， 且追求互不攻击的车最多;

2. 将行视为左部的点, 将列视为右部的点, 将车视为一条边;

3. 转化为求最多的边且不共点, 二分图最大匹配模型

#include <bits/stdc++.h>
using namespace std;

const int N = 210;
bool g[N][N];
bool st[N];
int match[N];
int n, m, t;

bool find(int u)
{
    for (int i = 1; i <= m; i++)
        if (!g[u][i] && !st[i])
        {
            st[i] = true;

            if (!match[i] || find(match[i]))
            {
                match[i] = u;
                return true;
            }
        }

    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    

    cin >> n >> m >> t;

    int x, y;
    while (t--)
    {
        cin >> x >> y;

        g[x][y] = true;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(st, 0, sizeof st);

        if (find(i)) cnt++;
    }

    cout << cnt;


    return 0;
}

P1129 [ZJOI2007] 矩阵游戏

P2071 座位安排

新技能:分点，x + n

P2055 [ZJOI2009] 假期的宿舍

题意:n个学生, m组认识关系, 问是否所有在校和外校都有床

1. 在校且回家的学生不要参与建模;

2. 留校生向自己的床连边, 向自己认识的在校生的床连边;

4. 检查最大匹配==留校生+外校生之和

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
int c[N], a[N];
int g[N][N];
int match[N];
bool st[N];
int n;

bool find(int u)
{
    for (int i = 1; i <= n; i++)
        if (!st[i] && c[i] && g[u][i])
        {
            st[i] = true;

            if (!match[i] || find(match[i]))
            {
                match[i] = u;
                return true;
            }
        }

    return false;
}

bool check()
{
    for (int i = 1; i <= n; i++)
    {
        memset(st, 0, sizeof st);

        if ((!c[i] || !a[i]) && !find(i)) return false;
    }

    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        cin >> n;

        memset(match, 0, sizeof match);

        for (int i = 1; i <= n; i++) cin >> c[i];

        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];

            if (!c[i]) a[i] = 1;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                cin >> g[i][j];

            if (c[i]) g[i][i] = 1;
        }

        if (check()) cout << "^_^\n";
        else cout << "T_T\n";
    }


    return 0;
}

二分图最小点覆盖

对于一张二分图G, 选取最小的点集S, 使得点集内的点能覆盖所有的边(任意一条边有一个端点在S中)

$二分图最小点覆盖 == 二分图最大匹配$

? 为什么

$证明:$

假设点集大小为S, 最大匹配为E

由于至少需要覆盖E条边, 而这E条边不共点, 那么S>=E

从S中每个点出发一定可以得到一条边, 不共点(为什么->有没有可能一条边的两个端点都在S中， 有可能，非常容易构造), 进而形成S组匹配, S<=E

因为E<=S<=E 所以S=E

模板题 Machine Schedule

二分图最小点覆盖建模的特征: 至少二选一!!!

意思就是说一条边的两个端点至少有一个在点集里

1. 把A机器的所有模式 看作左部的点

2. 把任务看作连边;

3. 追求最少的重启时间, 等价于追求最少的模式完成所有的任务

4. 若任务可以在0模式完成， 不要建边！！！, 因为一开始的时候就可以完成

P6062 [USACO05JAN] Muddy Fields G

1. 贪心的考虑,木板越长越好

2. 泥地要吗被横向覆盖, 要么被纵向覆盖, 可以重叠；

横向搜索所有连续的泥地, 纵向搜索所有连续的泥地, 当作一个”大点”;

4. 把行和列看作二分图的左部和右部, 把泥地当作边;

二分图最大独立集问题

在一张二分图G中, 选取最大的点集S, 点集内没有连边

二分图最大独立集问题 = 总点数 - 最小点覆盖

“模板”题 骑士共存问题

用红色和黄色划分二分图

$尽量向下移动可以使时间更优$

长脖子鹿放置

1. 棋子只会共计与其所在行的编号奇偶不同的位置

2. 将奇数行和偶数行视为二分的左右部;

3. 枚举左部的点(行的编号)， 至多连4条边

4. 跑最大独立集即为答案

P6268 [SHOI2002] 舞会

1. 将跳舞的人编号标记, 从1开始

2. 对于跳舞的人的跑一遍二分图,染色;

3. 颜色1的点向颜色2的点建有向边， 跑最大匹配

ans = n - 最大匹配

$最大团$

对于无相图G，其最大的一个子图G’, 满足G’中任意两点都有直接连边，那么称G’是G的一个最大团

$补图$

对于无向图G, 其补图是指原本不连边的两个点都连边，原本连边的点都不连边

若无向图G的补图是二分图, 那么找G的最大团等价于找补图的最大独立集

P3731 [HAOI2017] 新型城市化

题意：

1. n个点， m条非连边关系;

2.至多有2个团

3.加1条边, 使得最大团得点数加1；

目标：求合法的加边点对.

n <= 1e4, m <= 1e5

分析

1. 补图是二分图，加边变成了删边;

2. 最大团 = 补图得最大独立集 = 总点数 - 补图得最大匹配

3. 转化为补图产出一条边，使得最大匹配数减1；

4. 最大匹配得必选边是指虽有最大匹配得方案中都含有得边, 反之是可选边

5. 一种方法是对于补图先跑一遍最大匹配一次枚举匹配边并标记，然后重新跑匈牙利，若最大匹配变少，则选取得就是必选边。

时间复杂度: $O(N^2M)$ 60tps

100tps 需要网络流

最小路径点覆盖问题

给定有向无环图G, 用最少的不相交的路径覆盖所有的点.

路径不相交, 就是指一个点恰好出现在一条路径上

模型:

1. 对于原图中的任一点x, 拆点为出点和入点

2. 对于原图中的一条有向图x -> y, 改为out[x] 指向 in[y]

3. 最少路径数量 = 原图点数n - 二分图的最大匹配

$----------$

证明:

$ 1. 所有路径不相交， 那么路径数等价于终点数; $
$ 2. 终点没有出边; $
$ 3. 当x-out没有参与最大匹配时, x必是终点 $
$ 4. 当参与最大匹配的out[x]最多, 作为路径终点的x最少 $

$----------$

4. 维护out[x]表示左部点x是否参与匹配

5. 枚举所有没有匹配成功(!out[i])的点, 则match[i-in]在原图指向i循环迭代即可找到一条路径

模板题

#include <bits/stdc++.h>
using namespace std;

const int N = 155, M = 6010;
int h[N], e[M], ne[M], idx;
bool st[N];
int match[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int find(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (!st[j])
        {
            st[j] = true;

            if (!match[j] || find(match[j]))
            {
                match[j] = u;
                return true;
            }
        }
    }

    return false;
}

void print(int u)
{
    if (!match[u])
    {
        cout << u << ' ';
        return;
    }

    print(match[u]);

    cout << u << ' ';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    

    int n, m;
    cin >> n >> m;

    memset(h, -1, sizeof h);

    int a, b;
    while (m--)
    {
        cin >> a >> b;

        add(b, a);
    }

    int cnt = 0;
    vector<int> g;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++) st[j] = false;

        if (find(i)) cnt++;
        else g.push_back(i);
    }

    for (auto i : g)
    {
        print(i);
        cout << '\n';
    }

    cout << n - cnt;


    return 0;
}

UVA1201 Taxi Cab Scheme

1. 一辆出租车就是一条路径;

2. 一个客人只需要坐一辆出租车

3. 上一个客人到达的时间 + 上一个客人到达的终点与下一个人的七点的麦哈顿距离 + 1 <= 下一个客人发出的时间

HDU-3861 The King’s Problem

1. 若图是DAG(有向无环图), 那么同一个州只可能是一条路径;

2. 先跑tarjan变成一个DAG, 再跑最少路径点覆盖即可