Zth's Blog

记录学习路上的点滴

0%

二分图

发表于 分类于

二分图相关问题

二分图

定义

如果一张图$G(V, E)$中的点集$V$可以被分成$A, B$两个集合， $A \cup B = V, A \cap B = \oslash$并且$A, B$集合内部的任意两点之间没有连边， 那么$G$是一张二分图， $A, B$中的点被称为左右部点

判定

如果$G$中不存在奇环， 那么$G$是一张二分图

具体操作是对$G$染色， 一条边上的两个点染不同的颜色， 能染成功就是二分图， 否则不是

二分图最大匹配

从二分图中选出最多的边， 满足任意两条边没有公共端点， 边的数量即为二分图的最大匹配数

最大独立集与最小点覆盖

最大独立集和最小点覆盖并不是只有在二分图中才有， 只不过在一般图中求解这两个东西是$NPC$问题， 但是在二分图中有多项式解法， 所以一般只有二分图中会用到

最大独立集

一张图$G(V, E)$， 从中选出最多的点， 满足任意两个点之间在$G$中没有边相连， 选出的点集称为$G$的最大独立集

最小点覆盖

一张图$G(V, E)$， 从中选出最少的点， 满足这些点覆盖了$G$所有的边， 选出的点集称为$G$的最小点覆盖

两者之间的关系

$|最大独立集| = |V| - |最小点覆盖|$

正确性显然：

选出最多的点构成独立集

$\Longleftrightarrow$删除最少的点使得剩下的点之间没有边

$\Longleftrightarrow$用最少的点覆盖所有的边

二分图匹配

模板采用洛谷P3386

匈牙利算法

时间复杂度$O(nm)$

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
#include <iostream>
#include <cstdio>
#include <cstring>

const int MAXN = 1003;
int n, m, e;
int tot, head[MAXN];
bool vis[MAXN << 1];
int match[MAXN << 1];
int ans;
struct Edge
{
	int from, to,next;

	Edge(int from = 0, int to = 0, int next = 0) : from(from), to(to), next(next) {}
} edge[MAXN * MAXN];

void Addedge(int u, int v)
{
	edge[++ tot] = Edge(u, v, head[u]);

	head[u] = tot;
}

bool Dfs(int x)
{
	for(int i = head[x]; i; i = edge[i].next)
	{
		int v = edge[i].to;

		if(! vis[v])
		{
			vis[v] = true;

			if(!match[v] || Dfs(match[v]))
				{match[v] = x; return true;}
		}
	}

	return false;
}

int main()
{
	scanf("%d%d%d", &n, &m, &e);

	for(int i = 1; i <= e; i ++)
	{
		int u, v;

		scanf("%d%d", &u, &v);

		if(v > m) continue;

		Addedge(u, v + n);
	}

	for(int i = 1; i <= n; i ++)
	{
		memset(vis, false, sizeof(vis));

		if(Dfs(i)) ans ++;
	}

	printf("%d", ans);

	return 0;
}

Dinic

时间复杂度$O(m \sqrt n)$

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

int n, m, E;
int s, t;
int tot = 1, head[2003];
struct Edge
{
    int from, to, next, cost;
} edge[200005];
int level[200005], maxflow;
std:: queue<int> Q;

void Addedge(int u, int v, int e)
{
    edge[++ tot] = (Edge) {u, v, head[u], e};

    head[u] = tot;
}

bool Dinic_Bfs()
{
    memset(level, 0, sizeof(level));
    while(Q.size()) Q.pop();

    level[s] = 1;
    Q.push(s);

    while(Q.size())
    {
        int u = Q.front(); Q.pop();

        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;

            if(level[v] || !edge[i].cost) continue;

            level[v] = level[u] + 1;
            Q.push(v);
        }
    }

    return level[t];
}

int Dinic_Dfs(int u, int flow)
{
    if(u == t) return flow;

    int out = 0;

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;

        if(level[v] != level[u] + 1 || !edge[i].cost) continue;

        int k = Dinic_Dfs(v, std:: min(flow, edge[i].cost));

        edge[i].cost -= k;
        edge[i ^ 1].cost += k;
        out += k;
        flow -= k;
    }

    if(! out) level[u] = 0;

    return out;
}

void Dinic()
{
    while(Dinic_Bfs()) maxflow += Dinic_Dfs(0, 1e9);
}

int main()
{
    scanf("%d%d%d", &n, &m, &E);
    for(int i = 1; i <= E; i ++)
    {
        int u, v;
        scanf("%d%d", &u, &v);

        Addedge(u, v + n, 1);
        Addedge(v + n, u, 0);
    }

    for(int i = 1; i <= n; i ++) Addedge(0, i, 1), Addedge(i, 0, 0);
    for(int i = 1; i <= m; i ++) Addedge(i + n, n + m + 1, 1), Addedge(n + m + 1, n + i, 0);

    s = 0;
    t = n + m + 1;

    Dinic();

    printf("%d\n", maxflow);

    return 0;
}

二分图的最大独立集与最小点覆盖

定理： $|二分图最小点覆盖| = |二分图最大匹配|$

最小点覆盖

匈牙利算法

求完最大匹配后， 从左部所有非匹配点开始再次寻找增广路(执行一遍Dfs)， 标记过程中访问过的点

最小点覆盖即为左部未被标记的点+右部被标记的点

Dinic

求完最大匹配后， 再Bfs一次， 标记过程中访问过的点

$G(V, E)$, $E$中所有连接已被标记点$x$和未被标记点$y$的边$E^{cut}$的端点， 也就是割边的点(去掉原点汇点)

实操就是左部未标记的点+右部被标记的点

最大独立集

即为最小点覆盖的补

放个题

牛客22年十一集训第三场的f

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

int n;
int a[5123];
struct Edge
{
    int from, to, next, cost;
};
struct Graph
{
    int tot, head[5123];
    Edge edge[2123456];

    void Addedge(int u, int v, int e)
    {
        edge[++ tot] = (Edge){u, v, head[u], e};

        head[u] = tot;
    }
} og, bg;
int s, t;
int c[5123], level[5123];
bool marked[5123];
std:: queue<int> Q;
int maxflow, ans;

void Color(int u, int color)
{
    c[u] = color;
    for(int i = og.head[u]; i; i = og.edge[i].next)
    {
        int v = og.edge[i].to;

        if(c[v]) continue;

        Color(v, color ^ 1);
    }
}

void Build()
{
    bg.tot = 1;

    for(int j = 1; j <= n; j ++)
        if(c[j] == 2)
        {
            bg.Addedge(s, j, 1);
            bg.Addedge(j, s, 0);

            for(int i = og.head[j]; i; i = og.edge[i].next)
            {
                int v = og.edge[i].to;

                bg.Addedge(j, v, 1);
                bg.Addedge(v, j, 0);
            }
        }
        else
            bg.Addedge(j, t, 1), bg.Addedge(t, j, 0);
}

bool Dinic_Bfs()
{
    memset(level, 0, sizeof(level));
    while(! Q.empty()) Q.pop();

    level[s] = 1; Q.push(s);

    while(! Q.empty())
    {
        int u = Q.front();
        Q.pop();

        marked[u] = true;

        for(int i = bg.head[u]; i; i = bg.edge[i].next)
        {
            int v = bg.edge[i].to;

            if(level[v] || !bg.edge[i].cost) continue;

            level[v] = level[u] + 1; Q.push(v);
        }
    }

    return level[t];
}

int Dinic_Dfs(int u, int upflow)
{
    if(u == t) return upflow;

    int useflow = 0;

    for(int i = bg.head[u]; i; i  = bg.edge[i].next)
    {
        int v = bg.edge[i].to, e = bg.edge[i].cost;

        if(level[v] != level[u] + 1 || !e) continue;

        int tmpflow = Dinic_Dfs(v, std:: min(upflow, e));

        bg.edge[i].cost -= tmpflow;
        bg.edge[i ^ 1].cost += tmpflow;

        upflow -= tmpflow;
        useflow += tmpflow;
    }

    if(! useflow) level[u] = 0;

    return useflow;
}

void Dinic()
{
    while(Dinic_Bfs()) maxflow += Dinic_Dfs(s, 10000000);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    s = n + 1;
    t = n + 2;

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            int tmp = 0;
            for(int k = 0; k <= 30; k ++)
                tmp += (((a[i] >> k) & 1) ^ ((a[j] >> k) & 1));

            if(tmp == 1)
                og.Addedge(i, j, 0);
        }

    for(int i = 1; i <= n; i ++)
        if(!c[i])
            Color(i, 2);

    Build();

    Dinic();

    memset(marked, 0, sizeof(marked));
    Dinic_Bfs();

    ans = n - maxflow;

    printf("%d\n", ans);
    for(int i = 1; i <= n; i ++)
        if((c[i] == 2 && marked[i]) || (c[i] == 3 && !marked[i]))
            printf("%d ", a[i]);
    printf("\n");

    return 0;
}

这题有个小技巧， 我判断两个数二进制是不是只有一位不同是枚举了30位， 实际上只要判断两个数的异或等不等于这两个数异或的$lowbit$就可以了