算法竞赛进阶指南 0x68 二分图的匹配

相关概念

对于一个无向图，节点的数N>=2，如果节点可以划分为两个非空集合A,B 满足

1. A与B的交集为空
2. 同一集合中的点没有边相连

A，B分别叫 左部 ， 右部

二分图的判定

方法

染色判定法。

由二分图的定义可以知道，如果i位于A中，那么与i连接的边一定在B中，这样遍历所有的边，如果没有矛盾，就说明是二分图。

充要条件

没有奇度数的环

代码实现

1

AcWing257. 关押罪犯

S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1∼N。

他们之间的关系自然也极不和谐。

很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。

我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。

如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。

公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。

他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。

假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

第一行为两个正整数 N 和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 M 行每行为三个正整数 aj，bj，cj，表示 aj 号和 bj 号罪犯之间存在仇恨，其怨气值为 cj。

数据保证 1≤aj**<bj**<N,0<cj≤109 且每对罪犯组合只出现一次。

输出格式

输出共 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
1
2
3
4
5
6
7

输出样例：

3512
1

对于二分图，天生就是让处于同一集合的节点之间没有边。

但是现在是最优化问题，要想转化为二分图的可行性问题，需要进行二分答案。

#include 
using namespace std;
#define N 20005
#define M 200007
int n, m;
int head[N], tot, ver[M], nxt[M], edge[M];
int v[N];
inline void add(int x, int y, int z)
{
    ver[++tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}

bool dfs(int x, int mid, int color)
{
    v[x] = color;
    for(int i = head[x]; i; i = nxt[i])
    {
        if(edge[i] <= mid) continue;
        int y = ver[i];
        if(!v[y])
        {
            if( !dfs(y, mid, 3-color) ) return false;
        }
        else
        {
            //还可以写作if(v[y] != 3-color)
            if(v[y] == color)//表示y的颜色与x的相同
            {
                return false;
            }
        }
    }
    return true;
}

bool judge(int mid)
{
    for(int i = 1; i <= n; i++) v[i] = 0;
    for(int i = 1; i <= n; i++) {
        if(!v[i]) 
            if(!dfs(i, mid, 1)) return false;
    }
    return true;
}

int main()
{
    tot = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    int l = 0, r = 1e9;
//号外：l的初始值应该是0，虽然每一个罪犯之间都有矛盾，但是如果是只有两个罪犯，那么就不会有冲突！
    while(l < r)
    {
        int mid = (l+r)>>1;
        if(judge(mid)) r = mid;
        else l = mid+1;
    }
    printf("%d", l);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

AcWing372. 棋盘覆盖

给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数 N 和 t，其中 t 为禁止放置的格子的数量。

接下来 t 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。

输出格式

输出一个整数，表示结果。

数据范围

1≤N≤100,

0≤t≤100

输入样例：

8 0
1

输出样例：

32
1

二分图的最大匹配

二分图的一组匹配：任意两条边都没有公共的端点。

二分图的最大匹配：在一个二分图中包含边数最多的匹配。

有匹配边，非匹配边，匹配点，非匹配点，意会即可。

交错路（增广路）：从一个非匹配点到另一个非匹配点的路径，其中路径满足匹配边以及非匹配边交错出现。

如果存在一个交错路，那么把匹配边变成非匹配边，把非匹配边变成匹配边，就可以实现匹配的边的数目增加一。

二分图的最大匹配的充要条件为不存在交错路

从左向右，证明逆否命题：如果存在交错路，那么有上述方法使得总的匹配数目增加，所以原来的匹配并不是最大匹配

从右向左，假设已经不存在交错路，但是仍然有一种更优的匹配方法，那么需要在现有的基础上进行改进，因为匹配的数目增加，所以要引入非匹配点。（暂时不会证明）

在实现的时候，算法时在左面开始寻找一个交错路，由于具有对称性，所以无论从哪里开始寻找都是可以的。

贪心策略

对于一个匹配点

1. 仅仅找到经过这一个点的交错路的时候，才值得变换与这个点匹配的另一个点
2. 不可能退回到没有匹配的情况。

代码的实现：

bool dfs(int x)
{
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(v[y]) continue;
        v[y] = 1;//要注意初始化
        if(!match[y] || dfs(match[y]))//不是dfs(y)
        {
            match[y] = x;
            return true;
        }
    }
    return false;
}

//main
//遍历左部，依次对于每一个点求有没有交错路，如果有，那么匹配的边就加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

采用二分图的匹配来进行解决现实问题所注意的点

有两个条件：

• 1条件：每一个节点最多与一条边相连。
• 0条件：同一个集合的节点之间不能有任何边相连。
• 思考思路：每一条边就是一个合法情况。

AcWing372. 棋盘覆盖

给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数 N 和 t，其中 t 为禁止放置的格子的数量。

接下来 t 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。

输出格式

输出一个整数，表示结果。

数据范围

1≤N≤100,

0≤t≤100

输入样例：

8 0
1

输出样例：

32
1

由于每一个格子仅仅可以使用一次，那么满足“1条件”

所以每一个格子就是一个节点。

边是连接相邻的两个格子，对于格子做如下划分，就可以得到两个集合。

其中，

• 蓝色格子有一个特征，那就是横坐标加上纵坐标是奇数；
• 红色格子有一个特征，那就是横坐标加上纵坐标是偶数。

合法性的条件： 1.不能越界，2.不能处于被 ban 的地位。

#include 
using namespace std;
#define N 105
bool ban[N][N];
int n, m;
int px[] = {-1, 0, 1, 0};
int py[] = {0, 1, 0, -1};
//大小为什么是2*N*N呢？因为左部点有N/2个，由于要给上下左右添加边，所以需要N/2*2*2.
int head[N*N], tot, ver[2*N*N], nxt[2*N*N];
int match[N*N];//表示右边的集合是否已经匹配，如果为0，那么就没有匹配。
bool v[N*N];

inline void add(int x, int y)
{
   ver[++tot] = y;
   nxt[tot] = head[x];
   head[x] = tot;
}

bool dfs(int x)
{
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(v[y]) continue;
        v[y] = 1;//要注意初始化
        if(!match[y] || dfs(match[y]))//不是dfs(y)
        {
            match[y] = x;
            return true;
        }
    }
    return false;
}

int main()
{
    tot = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ban[x][y] = true;
    }   
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(ban[i][j] || ((i+j)&1) != 0) continue;//指的是红色格子
            for(int k = 0; k < 4; k++)
            {
                int x = i+px[k], y = j+py[k];
                if(x < 1 || x > n || y < 1 || y > n || ban[x][y]) continue;
                add((i-1)*n+j, (x-1)*n+y);//注意不是i*n+j
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(ban[i][j] || ((i+j)&1) != 0) continue;//指的是红色格子
            memset(v, 0, sizeof(v));
                if(dfs((i-1)*n+j))
                    ans ++;
        }
    }
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

AcWing373. 車的放置

给定一个 N 行 M 列的棋盘，已知某些格子禁止放置。
问棋盘上最多能放多少个不能互相攻击的車。
車放在格子里，攻击范围与中国象棋的“車”一致。

输入格式

第一行包含三个整数 N,M,T，其中 T 表示禁止放置的格子的数量。

接下来 T 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。

输出格式

输出一个整数，表示结果。

数据范围

1≤N,M≤200

输入样例：

8 8 0
1

输出样例：

8
1

对于这一道题，考虑二分图的最大匹配

由于每一行以及每一列仅仅可以放置一个車，所以可以把每一行，每一列看做是节点。

合法的情况是在一个点上（把满足条件的点建立行以及列的联系）。

这样也满足“0条件”

#include 
using namespace std;
#define N 205
bool ban[N][N];
int n, m, t;
//1~n表示行，n+1~m+n表示列
int head[2*N], tot, ver[N*N], nxt[N*N];
int v[N*2], match[N*2];

inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

bool dfs(int x)
{
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(v[y]) continue;
        v[y] = true;
        if(!match[y] || dfs(match[y]))
        {
            match[y] = x;
            return true;
        }
    }
    return false;
}

int main()
{
    tot = 1;
    cin >> n >> m >> t;
    while(t--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ban[x][y] = true;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(ban[i][j]) continue;
            add(i, j+n);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        memset(v, 0, sizeof(v));//在进行二分图匹配的时候，一定要注意v的清零
        if(dfs(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

如果是图比较稠密以至于到达了枚举的级别，那么就不必要建一张邻接表了。在dfs中枚举y

二分图的完备匹配

概念：

给定一个二分图，满足：

1. 左部，右部节点数相同
2. 最大匹配包含n条匹配边

那么就称这一个二分图具有完全匹配

二分图的多重匹配

左部有 N 个节点，右边有 M 个节点。

左部的第 i 个节点最多可以匹配a[i]个右部节点。

右部的第 j 个节点最多可以匹配b[j]个左部节点。

解决方案

1. 像背包问题一样，进行拆点，然后应用匈牙利算法。
2. main函数中遍历的时候，让左部的第 i 个节点执行匹配右部节点a[i]次。（当右部的匹配数全部是1）
3. （当右部部是多重的，左部的a[i]全部是1，对于右部的节点，如果没有超过匹配次数，那么就匹配，否则对这一个右部点所有的匹配进行递归）
4. 使用网络流。

AcWing374. 导弹防御塔

Freda 的城堡遭受了 M 个入侵者的攻击！

Freda 控制着 N 座导弹防御塔，每座塔都有足够数量的导弹，但是每次只能发射一枚。

在发射导弹时，导弹需要 T1 秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要 T2 分钟来冷却。

所有导弹都有相同的匀速飞行速度 V，并且会沿着距离最短的路径去打击目标。

计算防御塔到目标的距离 Distance 时，你只需要计算水平距离，而忽略导弹飞行的高度。

导弹在空中飞行的时间就是 (Distance**/**V) 分钟，导弹到达目标后可以立即将它击毁。

现在，给出 N 座导弹防御塔的坐标，M 个入侵者的坐标，T1**,T2** 和 V。

因为 Freda 的小伙伴 Rainbow 就要来拜访城堡了，你需要求出至少多少分钟才能击退所有的入侵者。

输入格式

第一行五个正整数 N,M,T1**,T2**,V。

接下来 M 行每行两个整数，代表入侵者的坐标。

接下来 N 行每行两个整数，代表防御塔的坐标。

输出格式

输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。

数据范围

1≤N,M≤50,坐标绝对值不超过 10000，T1**,T2**,V 不超过 2000。

输入样例：

3 3 30 20 1
0 0
0 50
50 0
50 50
0 1000
1000 0
1
2
3
4
5
6
7

输出样例：

91.500000
1

看起来貌似很复杂，但是不要让害怕迷惑心智

这一道题目貌似感觉是多重匹配问题，但是由于有时间在干扰，导致这一道题目比较难。

多重匹配仅仅在于使得匹配到的数目尽可能多，并没有涉及如何分配才能够使得时间最小。

这个时候，而已考虑二分，由于最短的时间满足单调性，并且经过二分，就把时间的最小值转化为可不可以找到一种匹配，回到了多重匹配问题。

图可以通过：

• 邻接矩阵
• 邻接表
• vector

实现，在这里，为了方便，采用vector

#include 
using namespace std;
#define N 55
int n, m;
double t1, t2, v;
struct {
    int x, y;
}a[N], b[N];//a表示入侵者的坐标，b表示防御塔的坐标
double dist[N][N];//表示的是一枚导弹从塔到入侵者所需要的时间（非距离）
vector<int> ver[N];//敌人所对应的某一时刻的某一座防御塔。
//N*N的原因：
//防御塔最多有N座，并且最多发射N枚炮弹（足够打败所有的敌军）p = min(m, p);
bool vis[N*N]; 
int match[N*N];

bool dfs(int x)
{
    for(int i = 0; i < ver[x].size(); i++)
    {
        int y = ver[x][i];
        if(vis[y]) continue;
        vis[y] = 1;
        if(!match[y] || dfs(match[y]))
        {
            match[y] = x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    cin >> n >> m >> t1 >> t2 >> v;
    t1 /= 60;//注意秒与分钟的转化
    for(int i = 1; i <= m; i++) scanf("%d%d", &a[i].x, &a[i].y);
    for(int i = 1; i <= n; i++) scanf("%d%d", &b[i].x, &b[i].y);
    double l = 0, r = 1e6;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = sqrt((a[i].x - b[j].x) * (a[i].x - b[j].x) + (a[i].y - b[j].y) * (a[i].y - b[j].y)) / v;
    while(r - l > 1e-9)//如果是-8，那么就会产生卡精度的问题，可以适当往小放
    {
        double mid = (l+r) / 2;
        //计算一座防御塔在规定的时间内最多可以发射多少枚导弹
        int p = (mid+t2)/(t1+t2)+1e-11;//加上一个比二分精度更小的数值
        p = min(m, p);//p是敌军数目以及在规定时间内打完的最小值。
        for(int i = 1; i <= m; i++)
        {
            ver[i].clear();//由于是多组情况，所以已改清已经有的边
            for(int j = 1; j <= n; j++)
            {
                for(int k = 1; k <= p; k++)
                {
                    if(dist[i][j] + t1*k + t2*(k-1) <= mid)
                        ver[i].push_back((j-1)*p+k);
                }
            }
        }
        int flag = true;
        memset(match, 0, sizeof(match));
        for(int i = 1; i <= m; i++)
        {
            memset(vis, 0, sizeof(vis));
            if(!dfs(i)){
                flag = false;
                break;
            }
        }
        if(flag) r = mid;
        else l = mid;
    }
    printf("%.6lf", r);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

二分图的带权匹配

二分图的带权最大匹配==二分图的最优匹配

条件：

1. 匹配数最大。
2. 所有匹配边加起来的权值最大。

有两种实现方法

• 费用流
• KM算法
  实现简单，在稠密图上效率高于费用流
  但是仅仅在带权最大匹配一定是“完备匹配”才可以。

交错树

对于匈牙利算法中，如果不能够找到交错路，那么从这一个点出发，最终的DFS结果是一棵树，第一层为左部节点，第二层为右部，第三层为左部节点。。。总共有奇数层。

奇数层与儿子节点连接的边是非匹配边，

偶数层与儿子节点连接的边是匹配边。

所以是一棵交错树。

相等子图

在二分图中，满足$A_i+B_j=w(i,j)$的所有边构成的子图。

（点的值已经给定，包含满足条件的边所构成的子图）