3.5.1 最大流
求解最大流的Ford-Fulkerson算法的邻接表实现的例子如下：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
using namespace std;
//求解最大流问题的基础代码
struct edge{int to, cap, rev;};
vector<edge> G[MAX_V]; //邻接表
bool used[MAX_V];
void add_edge(int from, int to, int cap){
//第三个参数反向边是在G[to]中来自from边（反向边）的index。
G[from].push_back((edge){to,cap,G[to}.size()});
//因为刚刚from的邻接表中加了一个元素，所以要得到正确的反向边的index，就要减一
G[to].push_back((edge){from,0,G[from}.size()-1}) }
int dfs(int v,int t,int f)
{
if(v == t)return f;
used[v] = true;
for(int i=0;i<G[v].size();i++)
{
edge &e = G[v][i];
if(!used[e.to] && e.cap > 0)
{
int d = dfs(e.to, t, min(f.e.cap));
G[e.to][e.rev].cap += d;
return d;
}
}
return 0;
}
int max_flow(int s, int t)
{
int flow = 0;
for(;;)
{
memset(used, 0, sizeof(used));
int f = dfs(s, t, INF);
if(f == 0) return flow;
flow += f;
}
}
记最大流的流量为F，那么该算法最多进行F次深度优先搜索，所以其复杂度为$O(F|E|)$。不过，这是一个很松的上界，达到这种最坏复杂度的情况几乎不存在。
3.5.7 应用问题
（其中的应用多转化为二分图的最大匹配问题）
有一个N*N的网格,该网格有K个小行星.你有一把武器,每次你使用武器发射光束可以攻击该网格特定行或列，从而清除行或列上的所有小行星.问你最少需要使用多少次武器能清除网格的所有小行星?
要破坏某个小行星，只能通过对应水平方向或者竖直方向的光束的攻击。利用攻击方法只有两种这一点，我们可以将问题按如下方法转换为图。
把光束当作图的顶点，而把小行星当作连接对应光束的边。这样转换之后，光束的攻击方案即对应一个顶点集合S，而要求攻击方案能够摧毁所有小行星，也就是图中的每条边都至少有一个属于S的端点，这样，这个问题就转化为了最小顶点覆盖问题。因为攻击方法只有两种，水平方向光束和竖直方向光束，那么这是一个二分图。最小覆盖问题通常是NP困难的，不过在二分图中等价于最大匹配问题，因而可以通过最大流算法高效地求解。
求解二分图的最大匹配问题可以看成是最大流问题的一种特殊情况。不妨对原图作如下变形：将原图中的所有无向边e改成有向边，方向从U到V（U和V是二分图中二分的顶点集），容量为1。增加源点s和汇点t，从s向所有顶点$u\in U$连一条容量为1的边，从所有的顶点$v\in V$向t连一条容量为1的边。
这样变形得到新图$G\prime$中的最大s-t流的流量就是原二分图G中最大匹配的匹配数，而U-V之间流量为正的边集合就是最大匹配。该算法的复杂度为$O(|V||E|)$。代码就是直接变形连线之后调用max_flow函数。下面给出基于匈牙利算法的二分图最大匹配数求解代码：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
using namespace std;
int V; //顶点数
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];
void add_edge(int u, int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
bool dfs(int v)
{
used[v] = true;
for(int i=0;i<G[v].size();i++)
{
int u = G[v][i], w = match[u];
if(w<0 || !used[w] && dfs(w))
{
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int bipartite_matching()
{
int res = 0;
memset(match, -1, sizeof(match));
for(int v=0;v<V;v++)
{
if(match[v]<0)
{
memset(used, 0, sizeof(used));
if(dfs(v))
{
res++;
}
}
}
return res;
}
int main()
{
int N, K;
int R[10010], C[10010];
cin >>N>>K;
for(int i=0;i<K;i++)
{
cin>>R[i]>>C[i];
}
V = N*2;
for(int i=0;i<K;i++)
{
add_edge(R[i]-1, N+C[i]-1);
}
cout<<bipartite_matching();
return 0;
}