源码:

二分图匹配

·图论

二分图概念:

分为两边的点,同边的点不相连,另一边的点可以相连,如图:


红色的边明显破坏了二分图性质。

匹配概念

两两个点进行匹配,匹配过的点不再出现,如图:

经过匹配后,点清除,其它的继续匹配。

最大匹配

一个二分图中,匹配最多的点数为这个二分图的最大匹配数。如图:

这里要注意,不是所有的二分图都有最大匹配数量=点数的情况。

算法介绍

总结两个二分图做法。

1.匈牙利算法

主要思路是贪心:我们需要满足后来的点时,可能需要破坏前面已经匹配的点,然后让前面的点换一个匹配对象。

题解:BYVoid-匈牙利算法

2.网络流

不得不说,一切图论皆网络流。

(吊打匈牙利不再话下)

入门篇:

网路流的概念和EK,Dinic

为什么选择网络流?

我们把每一条边的流量设置为1(反向边为0),建造源点和汇点(习惯是源点source=1,汇点sink=n+m+2),那么流到了汇点,最大流量就是网络流。

为什么呢?

通俗一点来说:因为所有流量都是1,所以每一个路径都有可行性(全都是增广路)。从源点出去的点(除了这个点没有连边)肯定都会出现增广路,那么流到右边点的,就是匹配成功(再流向汇点)。

这里的建模需要特别注意。

ISAP

更快的ISAP解法

ISAP是一种网络流算法,会比Dinic快很多,而且少了初始化BFS,程序复杂度少了很多,参考如下。

CODE

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
//可能因为pascal或者是初始化的原因,有些时候被Dinic赶超,不过时间复杂度还是很乐观的。(可以开O2)
//少了建模和添边,ISAP的DFS只占很少Byte。
//以下程序只是介绍建模部分

Uses math;

var
        value,reach:array[0..2010] of longint;
        dis,gap,cnt,next:array[1..1010] of longint;
        n,m,source,sink,tot,x,y,sum,i,k:longint;
        maxflow:int64;

procedure add(x,y,sum:longint);
begin
        inc(tot);
        reach[tot]:=y;
        inc(value[tot],sum);
        next[tot]:=cnt[x];
        cnt[x]:=tot;
end;

function Dfs(now,flow:longint):longint;
var
        i,k,mindis,ret:longint;
begin
        mindis:=n-1;
        ret:=flow;
        if now=sink then
                exit(flow);

        i:=cnt[now];
        repeat
                if value[i]>0 then
                begin
                        if dis[now]=dis[reach[i]]+1 then
                        begin
                                k:=Dfs(reach[i],min(ret,value[i]));
                                dec(value[i],k);
                                inc(value[i xor 1],k);
                                dec(ret,k);
                                if dis[source]>=n then
                                        exit(flow-ret);
                                if ret=0 then
                                        break;
                        end;
                        mindis:=min(mindis,dis[reach[i]]);
                end;
                i:=next[i];
        until i=-1;

        if ret=flow then
        begin
                dec(gap[dis[now]]);
                if gap[dis[now]]=0 then
                        dis[source]:=n;
                dis[now]:=mindis+1;
                inc(gap[dis[now]]);
        end;
        exit(flow-ret);
end;

begin
        filldword(cnt,sizeof(cnt) div 4,maxlongint*2+1);
        tot:=1;

        read(n,m,k);
        source:=1;
        sink:=n+m+2;
        for i:=1 to n do //源点向左边的点添边
        begin
                add(source,i+1,1);
                add(i+1,source,0); //注意:反向边依然是0
        end;
        for i:=1 to k do //创建二分图
        begin
                read(x,y);
                if (x>n)or(y>m) then //Bug
                        continue;
                add(x+1,y+n+1,1);
                add(y+n+1,x+1,0);
        end;
        for i:=1 to m do //右边的点向汇点添边
        begin
                add(i+n+1,sink,1);
                add(sink,i+n+1,0);
        end;

        n:=n+m+2;

        gap[source]:=n; //ISAP网络流部分
        while dis[source]<n do
                inc(maxflow,Dfs(source,maxlongint));
        writeln(maxflow);
end.