mydcwfy's Blog

二分图

Posted on
Symbols count in article: 4.8k Reading time ≈ 10 mins.

简单的前置知识。

1.定义

也就是能分成两部分，每部之间没有边。

二分图在染色法时（每边染色不同，且只有 2 种颜色）不产生矛盾。

同时，如果不满足染色法，一定不是二分图。

这个证明其实有点难，感性理解就是了（大雾

因为无法将颜色相同的点放入两部分，因为无论放入哪部分都会导致该部分内有边。

没有长度为奇数环（染色法没有矛盾）就一定是二分图。

证明：因为没有奇数环的图，那么自己如果能走回自己，一定是经过的偶数条边，而这样两次染的色是相同的，所以就不会产生矛盾。

例题：

关押罪犯 Luogu

关押罪犯 AcWing

这是一道典型的二分图判定题目。

虽然有其他做法，但今天着重讲二分图。

我们对这个图的操作明显就是二分图，而答案又是最大的影响最小化，所以根据套路，应该二分。

二分答案，对于每一个 $mid$，小于等于的不管，大于的加入边集，看会不会发生冲突。

用染色方法判定，时间复杂度为 $O(n\log\max(a_i))$

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e4+10,M=2e5+10;
int h[N],e[M],ne[M],idx,w[M];
int color[N],now,n,m;
bool res;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dfs(int x)
{
    if (!res) return;
    for (int i=h[x];~i;i=ne[i])
        if (w[i]>now)
        {
            if (color[x]==color[e[i]])
            {
                res=0;
                return;
            }
            if (color[e[i]]==0)
            {
                color[e[i]]=-color[x];
                dfs(e[i]);
            }
        }
}

bool check(int mid)
{
    memset(color,0,sizeof color);
    res=1;now=mid;
    for (int i=1;i<=n;++i)
        if (color[i]==0) color[i]=1,dfs(i);
    return res;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;int a,b,c;
    while (m--)
    {
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }
    int l=0,r=(int)1e9;
    while (l<r)
    {
        int mid=l+r>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}

2.求最大匹配—匈牙利算法

1） 匹配（定义一堆

我们让二分图的一些边作为匹配边，需要满足的条件是：这些边都没有共同的端点。匹配边两边的点是匹配点，反之就是非匹配点。

最大匹配就是所有匹配中最大的（废话，最大的评级是根据边数（其实根据点数也没有什么，因为点数等于边数的两倍，只是更为常见的定义是用边数。

2）增广路径

从非匹配点开始，沿着非匹配边、匹配边、非、匹、非走，最后走到非匹配点，这样的路径就是一条增光路径。

3）算法核心

最大匹配等价于没有增广路径。

必要性易证：如果有，一定可以这条增广路径上的所有边将所有都取反（匹配边变为非匹配，非匹配变为匹配边，就得到更大匹配。

画个图，其实比较直观。

（蓝色、红色是匹配边，黑色是非匹配边，左边红-黑交替的是增广路径，两端是非匹配点，将红-黑的所有边匹配取反，答案增加 1）

充分性略过。

4）Konig 定理

最小点覆盖 = 最大匹配。

最小点覆盖是指标记数量最少的点，使得每一条边至少有一个端点被标记。

证明又一次略。（主要是我太菜

5）算法流程

首先，枚举每一个点，然后看这个点有没有增广路径，如果有的话，直接取反，答案加 1。

具体来说，我们举一个实在的例子。

我们发现，$a$ 现在想要匹配 $b$，但是现在 $b$ 匹配着 $c$，如果我们要让 $a$ 匹配 $b$，那么我们就要给 $c$ 找到一个匹配，不然的话答案不会增加。又发现现在 $a$ 和 $c$ 是同一部分的，这个其实是一个相似的问题，我们对 $c$ 进行递归即可。直到递归到 $m$ 和 $a,c$ 是同一部分的，而且 $m$ 有一个非匹配点 $n$ 与之相连，那么，我们就将 $m$ 的匹配变为 $n$，递归回去，最后 $a$ 匹配 $b$，答案加一。

时间复杂度为 $O(nm)$，实际和 spfa 等类似，跑得飞快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool dfs(int x)//是看 x 能不能重新匹配一个，能就返回 true
{
    for (int i=h[x];~i;i=ne[i])
        if (!vis[e[i]])//vis 在每一次重新 a 开始的时候都要清空，是为了看一下有没有又走回来，就导致死循环了
        {
            vis[e[i]]=1;
            if (mat[e[i]]==0||dfs(mat[e[i]]))
            {
                mat[e[i]]=x;
                return true;
            }
        }
    return false;
}

3. 最小点覆盖

AcWing376 机器任务

可以发现，对于 $a(i)$ 和 $b(i)$，必须有一个被取。

而我们发现，对于每一个 $i\in[1,n]$，$a(i)$ 只需要重启一次，也就是说，我们对于每一个 $a(i)$，贡献仅为 1。

可以将 $a(i)-b(i)$ 转化为一条边，变成用最少的点让所有的边都有一个端点有标记，也就是最小点覆盖问题，用 Konig 定理转化为最大匹配，用匈牙利算法就可以了。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=250,M=1e5+10;
int h[N],e[M],ne[M],w[M],idx;
int n,m,k,mat[N],ans;
bool vis[N];

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

bool dfs(int x)
{
    for (int i=h[x];~i;i=ne[i])
        if (!vis[e[i]])
        {
            vis[e[i]]=1;
            if (mat[e[i]]==0||dfs(mat[e[i]]))
            {
                mat[e[i]]=x;
                return true;
            }
        }
    return false;
}

int main()
{
    while (cin>>n&&n)
    {
    memset(h,-1,sizeof h);
    memset(mat,0,sizeof mat);
    cin>>m>>k;
    int i,a,b;
    while (k--)
    {
        scanf("%d %d %d",&i,&a,&b);
        if (a>=1&&b>=1) add(a,b+n),add(b+n,a);
    }
    for (int i=0;i<n;++i)
    {
        memset(vis,0,sizeof vis);
        if (dfs(i)) ans++;
    }
    cout<<ans<<endl;
    ans=0;idx=0;
    }
    return 0;
}

4.最大独立集

AcWing378 骑士放置

Luogu P3355 骑士共存问题

对于每一条限制，相当于端点只能取一个。

也就是一个最大独立集的问题了。

大概又有一个简单的定理：最大独立集 = 总点数 - 最小点覆盖。

不会证，只有鸽着了。

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
#include<iostream>//AcWing 代码，Luogu n = m
#include<cstring>
#include<algorithm>
#include<cstdio>
#define PII pair<int,int>
using namespace std;

const int N=110;
PII mat[N][N];
int n,m;
bool v[N][N],vis[N][N];
int dx[]={2,2,1,1,-1,-1,-2,-2},
    dy[]={1,-1,2,-2,2,-2,1,-1};

bool check(int x,int y)
{
    if (x>=1&&y>=1) return x<=n&&y<=m;
    return false;
}

bool dfs(int x,int y)
{
    if (v[x][y]) return false;
    for (int k=0;k<8;++k)
    {
        int i=x+dx[k],j=y+dy[k];
        if ((!check(i,j))||v[i][j]||vis[i][j]) continue;
        vis[i][j]=1;
        int ii=mat[i][j].first,jj=mat[i][j].second;
        if (((ii==0)&&(jj==0))||dfs(ii,jj))
        {
            mat[i][j]=make_pair(x,y);
            // printf("%d %d:%d %d\n",x,y,i,j);
            return true;
        }
    }
    return false;
}

int main()
{
    int k,a,b;
    cin>>n>>m>>k;int tmp=k;
    while (k--)
    {
        scanf("%d %d",&a,&b);
        v[a][b]=1;
    }
    int res=0;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        {
            if (v[i][j]||(i+j)&1) continue;
            memset(vis,0,sizeof vis);
            if (dfs(i,j)) res++;
        }
    cout<<n*m-tmp-res<<endl;
    return 0;
}