二分图及其多个扩展用法详解及其证明 + 模板题： 关押罪犯 棋盘覆盖

首先说明我们要讲的知识点：

1：二分图不存在奇数环，染色法不矛盾：

2：匈牙利算法: 匹配，最大匹配，匹配点，增广路径

3：最小点覆盖，最大独立集，最小路径点覆盖，（最小路径重复点覆盖）。

      结论：最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖

首先我们先说：二分图 <---> 图中不存在奇数环 <--->染色法无矛盾这个结论有点明显，就不加证明了。。

例题：关押罪犯

来源：《算法竞赛进阶指南》, NOIP2010提高组

        

S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1∼N。
 
他们之间的关系自然也极不和谐。
 
很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。
 
我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。
 
如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。
 
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。
 
公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
 
在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。
 
他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。
 
假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
 
那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
 
输入格式
第一行为两个正整数 N 和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
 
接下来的 M 行每行为三个正整数 aj，bj，cj，表示 aj 号和 bj 号罪犯之间存在仇恨，其怨气值为 cj。
 
数据保证 1≤aj0109 且每对罪犯组合只出现一次。
 
输出格式
输出共 1 行，为 Z 市长看到的那个冲突事件的影响力。
 
如果本年内监狱中未发生任何冲突事件，请输出 0。
 
数据范围
N≤20000,M≤100000
输入样例：
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
输出样例：
3512

解题思路：

这题要用到二分，不懂二分的可以看看这篇。

(16条消息) 《二分模板详解》_wsh1931的博客-CSDN博客

将罪犯之间的怒气值大于mid分到为一组，即二分的右边，将罪犯之间的怒气值小于等于mid的分到左边：最优解即为大于mid的最小值即最小的满足条件的解。

证明二分的两段性：任意选取二分右边一个大于mid的数ans, 因为mid可以满足条件，则因为ans > mid即所要连接的边更少，即要连接的边是当罪犯怒气值大于mid的子类，因此右边成立。

反证法：任取左边一个小于等于mid的数ans，若ans能成立即说明大于mid的第一个数不是最优解，与最优解矛盾所以不成立。

#include 
#include 
#include 
 
using namespace std;
 
const int N = 20010, M = 200010;
 
int n, m;
int color[N];//表示N这个人是否被染色过这里我们假设1为白色，2为红色
int h[N], e[M], ne[M], w[M], idx;
 
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}
 
bool dfs(int u, int c, int mid)
{
    color[u] = c;//将点u染成颜色c
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (w[i] <= mid) continue;//将大于mid的罪犯的怒气染色。
        if (!color[j])
        {
            if (!dfs(j, 3 - c, mid)) return false;//将u的子节点染成不同于u的颜色
            //若c = 1则3 - c = 2
            //若c = 2则3 - c = 1
        }
        else if (color[j] == c) return false;//若j已经被染色且颜色与u相同说明出现矛盾
                
    }
    
    return true;//排除了所有失败的结果。
}
 
bool check(int mid)
{
    memset(color, 0, sizeof color);//初始化
    
    for (int i = 1; i <= n; i ++ )
        if (!color[i]) //若 i 还未被染色
            if (!dfs(i, 1, mid)) return false;//若 i 染色失败
    return true;//排除了所有失败情况说明染色成功。
}
 
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    while (m -- )
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    int l = 0, r = 1e9;
    while (l < r)//该模板是找出满足条件的大于mid的最小值
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    cout << r << endl;
    
    return 0;
}

 2: 匈牙利算法: 匹配，最大匹配，匹配点，增广路径在此之前要直到匈牙利算法的算法思想。

匹配：每两个点之间相连所形成的边不存在公共点。

如图：

最大匹配：最大的匹配的数量。

匹配点：已经匹配的点即被边连接起来的点。

增广路径：从一个非匹配点出发按非匹配边 -> 匹配边 -> 分匹配边.....最后到另一边的非匹配点这样的路径即为增广路径。

如图：从点x到点y的路径即为一条增广路径

因此我们可以得出一个结论：

若存在最大匹配则一定没有增广路径：因为若是存在增广路径则增广路径开始的节点和增广路径结束的节点一定可以连一条边。

例题：棋盘覆盖

来源：算法竞赛进阶指南

给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。
 
求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
 
输入格式
第一行包含两个整数 N 和 t，其中 t 为禁止放置的格子的数量。
 
接下来 t 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。
 
输出格式
输出一个整数，表示结果。
 
数据范围
1≤N≤100,
0≤t≤100
输入样例：
8 0
输出样例：
32

由题意：

我们要找到任意两个骨牌不重叠的可以防止骨牌数目最多的方法：

假设一个图：

红色格子为不能防止的点，绿色格子为我们所选取的骨牌，我们可以把每个选取的骨牌从a到b连一条边，答案即为不能存在重复点的最大匹配数量。

现在要证明他是二分图：

如图将每个横纵坐标标号：可以得到结论坐标和为偶数的四个方向都是奇数，坐标和为奇数的四个方向都是偶数，因此我们可以把奇数分到二分图的左边，偶数分到二分图的右边，枚举每个坐标和为奇数（或偶数）的点找到能满足不存在重复点的最大匹配数量即为最终答案。 

代码如下：

#include 
#include 
#include 
 
#define x first
#define y second
 
using namespace std;
 
const int N = 110;
 
typedef pair<int, int> PII;
 
int n, m;
int g[N][N];//表示当前格子是否被禁止存放
bool st[N][N];//判断某个格子是否被用过防止重复遍历。
PII match[N][N];//match[a][b]表示坐标为(a, b)这个人是否有匹配的点。
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};//枚举四个方向
 
bool find(int x, int y)//匈牙利算法
{
    for (int u = 0; u < 4; u ++ )//枚举周围四个格子
    {
        int a = x + dx[u], b = y + dy[u];
        if (a < 1 || a > n || b < 1 || b > n) continue;//若越界
        if (st[a][b] || g[a][b]) continue;//若被遍历过或者该坐标不能放骨牌
        
        st[a][b] = true;
        PII t = match[a][b];
        if (t.x == -1 || find(t.x, t.y))//若(a, b)还没有匹配的点，或者(a, b)匹配的点还可以找到其他点
        {
            match[a][b] = {x, y};
            return true;//(a, b)匹配成功
        }
    }
    
    return false;//否则匹配失败
}
 
int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        g[a][b] = true;//第a行第b列禁止存放骨牌
    }
    
    memset(match, -1, sizeof match);
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if ((i + j) % 2 && !g[i][j])//找到坐标和为奇数的点且该点未被禁用
            {
                memset(st, 0, sizeof st);
                if (find(i, j)) res ++ ;//若(i, j)能找到匹配的点则答案++
            }
    
    cout << res << endl;
    
    return 0;
}

3：

最大匹配数 = 最小点覆盖。

最小点覆盖：所选择的点数最少且能够将所有的边都包括。

例题：机器任务

来源：算法竞赛进阶指南

有两台机器 A，B 以及 K 个任务。
 
机器 A 有 N 种不同的模式（模式 0∼N−1），机器 B 有 M 种不同的模式（模式 0∼M−1）。
 
两台机器最开始都处于模式 0。
 
每个任务既可以在 A 上执行，也可以在 B 上执行。
 
对于每个任务 i，给定两个整数 a[i] 和 b[i]，表示如果该任务在 A 上执行，需要设置模式为 a[i]，如果在 B 上执行，需要模式为 b[i]。
 
任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
 
求怎样分配任务并合理安排顺序，能使机器重启次数最少。
 
输入格式
输入包含多组测试数据。
 
每组数据第一行包含三个整数 N,M,K。
 
接下来 K 行，每行三个整数 i,a[i] 和 b[i]，i 为任务编号，从 0 开始。
 
当输入一行为 0 时，表示输入终止。
 
输出格式
每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。
 
数据范围
N,M<100,K<1000
0≤a[i]
0≤b[i]
输入样例：
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
输出样例：
3

解题思路：

我们将题目中的a[i]看作是左边图，b[i]看作是右边图，g[a][b]表示从点a到点b上连一条无向边，我们要找出最少重启的次数即在右边图中找出最少的点使它可以覆盖从a到b的所有边，即求出最小点覆盖，注意初始时机器的模式为0，所以当a 或者 b为0时直接跳过

#include 
#include 
#include 
 
using namespace std;
 
const int N = 110;
 
int n, m, k;
bool st[N];
int match[N];
bool g[N][N];
 
bool find(int a)
{
    for (int b = 0; b < m; b ++ )//求最大匹配数 == 最小点覆盖
    {
        if (st[b]) continue;
        if (!g[a][b]) continue;
        st[b] = true;
        if (match[b] == -1 || find(match[b]))
        {
            match[b] = a;
            return true;
        }
    }
    
    return false;
}
 
int main()
{
    while (cin >> n, n)
    {
        cin >> m >> k;
        memset(g, false, sizeof g);
        while (k -- )
        {
            int t, a, b;
            scanf("%d %d %d", &t, &a, &b);
            
            if (!a || !b) continue;//机器初始的状态为0
            
            g[a][b] = true;
        }
        
        int res = 0;
        memset(match, -1, sizeof match);//初始化
        
        for (int i = 0; i < n; i ++ )
        {
            memset(st, 0, sizeof st);
            if (find(i)) res ++ ;
        }
        
        cout << res << endl;
    }
    
    return 0;
}

4: 最大独立集 ：选出最多的点，使得选出的点之间没有边。

求最大独立集：选出最多的点，使得选出的点之间没有边《==》总点数 - 选出最小的点可以破坏所有的边 《==》最小点覆盖 《==》最大匹配数。

假设最大匹配数为m，共有n个点，即选出最小的点可以破坏所有的边的点数为m，此时最大独立集即为n - m;

例题：骑士放置

来源：算法竞赛进阶指南：

给定一个 N×M 的棋盘，有一些格子禁止放棋子。
 
问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。
 
输入格式
第一行包含三个整数 N,M,T，其中 T 表示禁止放置的格子的数量。
 
接下来 T 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。
 
输出格式
输出一个整数表示结果。
 
数据范围
1≤N,M≤100
输入样例：
2 3 0
输出样例：
4

如图：

图中的马可以攻击它周围的八个格子：又因为它能攻击到的格子横纵坐标之和为它本身坐标的横纵坐标之和加减abs(3) 因此它每次攻击到的其它马的横纵坐标之和与它本身的横纵坐标之和相反，所以我们可以将横纵坐标之和为偶数，以及横纵坐标之和为奇数的点分为两半，即此分法可以把它分为一个二分图。

由题意：每个马不能相互攻击到，即每点之间不能有独立的边，即求得是的它的最大独立集。

因此解题步骤为：

1：求出它的最小点覆盖假设为res。

2：最大独立集即为 n * m - res - k（k为被破坏的点。）

代码如下：

#include 
#include 
#include 
 
#define x first
#define y second
 
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 110;
 
int n, m, t;
bool st[N][N];//判断该点是否被用过
bool map[N][N];//记录该坐标是否被破坏
PII match[N][N];//记录与某个点所匹配的点
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};//八个方向
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
 
bool find(int a, int b)
{
    for (int i = 0; i < 8; i ++ )
    {
        int x = a + dx[i], y = b + dy[i];
        if (x < 1 || x > n || y < 1 || y > m) continue;
        if (st[x][y]) continue;
        if (map[x][y]) continue;
        
        st[x][y] = true;
        
        if (match[x][y].x == -1 || find(match[x][y].x, match[x][y].y))
        {
            match[x][y] = {a, b};
            return true;
        }
    }
    
    return false;
}
 
int main()
{
    cin >> n >> m >> t;
    
    for (int i = 0; i < t; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        map[a][b] = true;//a, b被破坏
    }
    
    memset(match, -1, sizeof match);//初始化
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if ((i + j) % 2 && !map[i][j])//枚举每个坐标和为奇数的点且该格子不能被破坏
            {
                memset(st, false, sizeof st);
                if (find(i, j)) res ++ ;
            }
            
    cout << n * m - res - t << endl;
    
    return 0;
}

 5：最小点路径覆盖：对于一个有向无环图，用最少的互不相交的路径将所有的点覆盖。（这里的最少的互不相交的路径是指：边不重复，点也不重复）。

拆点：对于原图中(1, n)拆为新图中的(1', n')；

转化：将原图中的i -> j 转化为新图中的i -> j'。

如图将原图中的1 -> 2 -> 3转化为新图的路径即为：

1 -> 2', 2 -> 3'。

但是不能出现1 -> 2, 3 -> 2这样点就重复了 

因此得出两个结论：

1：路径 《==》 匹配

2：左部非匹配点 《==》路径终点，孤立的点也算一种特别的终点

 所以要求原图中最少的互不相交的路径，即原图中终点最少的路径，即求新图中左侧最少的非匹配点的数量(n - m)，即求新图中左侧最大的匹配数量(m)，即求最大匹配数(m), 最后用左侧所有点数(n) - 最大匹配数(m)即为最少的互不相交的路径。

例题：P2764 最小路径覆盖问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#include 
#include 
 
using namespace std;
 
const int N = 310, M = 6010;
 
int ans;
int n, m;
bool st[N];
int match[N];
int h[N], e[M], ne[M], idx;
 
void add(int a, int b)//邻接表
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}
 
bool find(int a)//二分图的最大匹配
{
    for (int i = h[a]; i != -1; i = ne[i])
    {
        int b = e[i];
        if (st[b]) continue;
        st[b] = true;
        
        if (match[b] == -1 || find(match[b]))
        {
            match[b] = a;//要定义双向边以便找到路径
            match[a] = b;
            return true;
        }
    }
    
    return false;
}
 
void get_path(int x)//输出路径
{
    printf("%d ", x);
    while (x = match[x], x != -1)
    {
        x -= n;
        printf("%d ", x);
        st[x] = true;
    }
    
    puts("");
}
 
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(match, -1, sizeof match);
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b + n);//映射
    }
    
    ans = n;
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        if (find(i)) ans --;//最小点覆盖 = n - 最大匹配数
    }
    
    memset(st, 0, sizeof st);
    for (int i = 1; i <= n; i ++ )
        if (!st[i]) get_path(i);
    
    cout << ans << endl;
    
    return 0;
}

        

扩展：最小路径点重复点覆盖：在最小路径点覆盖的基础上加上边和点可以重复即为最小路径重复点覆盖。

步骤：假设原图为G

1：求原图G传递闭包G'

2：则原图G中最小路径重复点覆盖 = 新图G'中最小路径覆盖；

证明：

首先先清楚什么是传递闭包：假如一条路径a -> b -> c则我们直接将点b忽略从a -> c连一条边求传递闭包用的是floyd算法若不懂floyd算法的可以看看这篇博客：

floyd 算法模板详解(适合新手)_wsh1931的博客-CSDN博客

传递闭包求法：(1条消息) 题解：算法竞赛进阶指南 排序_wsh1931的博客-CSDN博客

即证明两个图G, G'等价。

在原图G中求传递闭包即将所有重复出现的点变为不重复出现的点：

即假设一条路径a -> b -> a -> e以点a为例根据传递闭包所形成的路径即为：

a -> b -> e.因此原图G中每一条路径在G'中都有路径与之配对即将重复的点跳过即为最小路径点覆盖.

同样将G'转化为G即将跳过的点还原，即将a -> b -> e还原为 a -> b -> a -> e。

因此G’中每一条路径都与G中每一条路径配对：即在G‘图中求最小路径点覆盖，即在G图中求最小路径重复点覆盖。

        

例题：捉迷藏

来源：算法竞赛进阶指南

Vani 和 cl2 在一片树林里捉迷藏。
 
这片树林里有 N 座房子，M 条有向道路，组成了一张有向无环图。
 
树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。
 
如果从房子 A 沿着路走下去能够到达 B，那么在 A 和 B 里的人是能够相互望见的。
 
现在 cl2 要在这 N 座房子里选择 K 座作为藏身点，同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找，为了避免被 Vani 看见，cl2 要求这 K 个藏身点的任意两个之间都没有路径相连。
 
为了让 Vani 更难找到自己，cl2 想知道最多能选出多少个藏身点。
 
输入格式
输入数据的第一行是两个整数 N 和 M。
 
接下来 M 行，每行两个整数 x,y，表示一条从 x 到 y 的有向道路。
 
输出格式
输出一个整数，表示最多能选取的藏身点个数。
 
数据范围
N≤200,M≤30000
输入样例：
7 5
1 2
3 2
2 4
4 5
4 6
输出样例：
3

根据题意两个点之间不能有路径重复。即求最小路径重复点覆盖 ==》求完传递闭包后求最小路径点覆盖答案为n - res。

#include 
#include 
#include 
 
using namespace std;
 
const int N = 210;
 
int n, m;
int match[N];
bool d[N][N], st[N];
 
bool find(int x)
{
    for (int i = 1; i <= n; i ++ )
    {
        if (d[x][i] && !st[i])
        {
            st[i] = true;
            
            if (match[i] == -1 || find(match[i]))
            {
                match[i] = x;
                return true;
            }
        }
    }
    
    return false;
}
 
int main()
{
    cin >> n >> m;
    
    while (m -- )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        d[a][b] = true;
    }
    
    for (int k = 1; k <= n; k ++ )//求传递闭包
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] |= d[i][k] & d[k][j];
    
    memset(match, -1, sizeof match);
    
    int res = 0;//求最大匹配数
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }
    
    cout << n - res << endl;//最小路径重复点覆盖 = 求传递闭包后的最小路径点覆盖 = n - res
    
    return 0;
}