二分图匹配

Posted on | In |
Words count in article: 1k | Reading time ≈ 5

如题所述，这类问题让我们求一个二分图的最大匹配，不知道二分图的同学请参考百度百科

看着那些术语让人头大对吧，那么来通俗一点的：给定若干个男生和若干个女生，每个男生都可以和一定数量的女生互相有好感，假定不存在同性恋和后宫，求最多能凑多少对CP（然后再统统烧了）。

对于这类问题通常有两种做法：匈牙利和网络流。

匈牙利算法

在我讲之前，我建议读者先去读一下Dark_Scope的这篇趣写算法系列之—匈牙利算法，相当的简单易懂。

那么我来用正经的话把他（她？）的语言翻译一遍：对于点集M中的每一个点u，找到与它配对的点v，如果点v尚未配对就把u、v配对，否则就试图给v的“原配”寻找新的配对点，找到后就把u、v配对。实际就是一个寻找增广路的过程。

相信有这些已经够清楚的了，以下是代码：

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 <bits/stdc++.h>
#define N 500000+110
using namespace std;
int n,m,s,cnt,ans;
int head[N],q[N],pre[N],mate[N];
bool vis[N];
struct edge
{
    int to,nxt;
}e[N];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline int add(int u,int v)
{
    e[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
inline bool Find(int u)
{
    for(register int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(!vis[v])
        {
            vis[v]=1;
            if(!mate[v]||Find(mate[v]))
            {
                mate[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    n=read(),m=read(),s=read();
    for(register int i=1;i<=s;i++)
    {
        int u=read(),v=read();
        if(v>m||u>n)
            continue;
        add(u,v);
    }
    for(register int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(Find(i))
            ans++;
    }
    printf("%d",ans);
    return 0;
}

网络流

很容易想到如果额外增加一个源点和一个汇点，然后就可以直接跑网络最大流了。

对于无权图，我们需要设置边权，很容易想到正向边为1，反向边为0，这样就可以很顺利的用Dinic跑出最大匹配了。

可以看出比匈牙利快多了（虽然没有$min(a,b)-1$算法快）

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;
const int N=2000000+110;
const int inf=0x7fffffff;
const int MAXN=50;
const double eps=1e-8;
il int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,m,k,cnt;
int head[N],q[N],dep[N],cur[N];
struct edge
{
	int to,nxt,weight;
};
edge e[N];
il void add_edge(int u,int v,int w)
{
	e[cnt]=(edge){v,head[u],w};
	head[u]=cnt++;
}
il bool BFS(int S,int T)
{
	int fr=1,tl=0;
	memset(dep,0,sizeof(dep));
	dep[S]=1;
	q[1]=S;
	while(tl<fr)
	{
		int u=q[++tl];
		for(ri i=head[u];i!=-1;i=e[i].nxt)
		{
			int v=e[i].to;
			if(!dep[v]&&e[i].weight>0)
			{
				dep[v]=dep[u]+1;
				q[++fr]=v;
			}
		}
	}
	if(!dep[T])
		return 0;
	return 1;
}
il int dfs(int u,int t,int flow)
{
	if(u==t)
		return flow;
	for(ri& i=cur[u];i!=-1;i=e[i].nxt)
	{
		int v=e[i].to;
		if(dep[v]==dep[u]+1&&e[i].weight>0)
		{
			int dis=dfs(v,t,min(flow,e[i].weight));
			if(dis>0)
			{
				e[i].weight-=dis;
				e[i^1].weight+=dis;
				return dis;
			}
		}
	}
	return 0;
}
il int Dinic(int S,int T)
{
	int ret=0;
	while(BFS(S,T))
	{
		for(ri i=0;i<=n+m+1;i++)
			cur[i]=head[i];
		while(int delta=dfs(S,T,inf))
			ret+=delta;
	}
	return ret;
}
int main()
{
	n=read(),m=read(),k=read();
	memset(head,-1,sizeof(head));
	for(ri i=1;i<=k;i++)
	{
		int u=read(),v=read();
		if(v>m)
			continue;
		add_edge(u,n+v,1);
		add_edge(n+v,u,0);
	}
	for(ri i=1;i<=n;i++)
	{
		add_edge(0,i,1);
		add_edge(i,0,0);
	}
	for(ri i=1;i<=m;i++)
	{
		add_edge(n+i,n+m+1,1);
		add_edge(n+m+1,n+i,0);
	}
	printf("%d",Dinic(0,n+m+1));
	return 0;
}
0%