今天这期对LC比赛来说有点超纲。因为一般LC出这类题的话，你能够用状压DP或者其他手段去解决的。而网络流是能够处理更大规模这类问题的算法。所以今天我们就来看一下，这类问题是怎么从状压DP入手解决，又是怎么从网络流来提升效率的。
House Robber
小伙伴LC刷的多的话，一定知道这个小偷偷房子的系列。在LC的题目中，房子是排成一条线，一棵树，或者一个环。那么要求是拿了一幢房子的财宝，它相邻2个房子的财宝就不能拿。问如何获得最大价值。
在线性的结构下，我们用一维DP即可解决这个问题。
dp[i] 代表到数组前I个的时候，最大的价值是多少。那么转移无非2种，一种是我取了最后一个房子的物品。那么dp[i] = dp[i - 2] + val[i]
或者我不取，那么dp[i] = dp[i - 1];
如果拓展到环上，我们只需要拆成2个子问题，从[0, n-1] 和 [1, n] 2个段去考虑
如果拓展到树上，就是维护2个变量，一个是拿当前节点可以有的最大值，一个是不拿可以有的最大值。那么处理完2个孩子之后，对自己的节点，就可以根据2个孩子的这2个信息。维护出自己的这2个信息，RETURN 到上层。
这3种类型的题目，小伙伴们可以自行去LC上学习，还是比较简单的。
扩展到2维
下面这个问题，我们把线性的房子，扩展到平面。我们给定一个矩阵，矩阵里的值就是房子的财宝数量。小偷拿了一个房子之后，它上下左右的房子是不能偷的。这个应该怎么做呢？
这个问题就需要用到状压DP了，因为前一层的拿法会影响到下一层的拿法。所以我们必须把前一层的所有拿法都算好。然后去算下一层的时候，就可以用O(1)的时间得到前一层对应的值。
dp[i][st] 就是代表我拿到第I层，第I层是ST的拿法，的最大价值是多少。
这个ST 其实是位压缩的值。比如1010 就代表拿了矩阵第i行的0号元素和2号元素。
所以这就要求这个矩阵的最大宽度是32.因为INT只有32位。如果真到了32位，这个时间复杂度也是会爆掉的。所以这类问题一般在1秒内大约可以解决长度在10-13的问题。
首先我们预处理第0行的，所有状态；注意有些是非法状态，比如相邻2个1. 0110 这种结构是会触发报警的，所以要避免。
避免也很简单(state & (state << 1)) != 0判断一下即可。
然后下面是3层循环，第一层是遍历层数，然后看前一层的状态，和这一层的状态。我们要过滤掉左右相邻的就是用上述方法。
随后上下相邻的过滤法也很简单
(state & prestate) != 0
我们可以看下代码
public int houseRobber5(int[][] houses) {
int h = houses.length, l = houses[0].length;
int n = 1 << l;
int[][] dp = new int[2][n];
for (int s = 0; s < n; s++) {
if ((s & (s << 1)) != 0) continue;
dp[0][s] = sum(s, houses[0]);
}
int ans = 0;
for (int i = 1; i < h; i++) {
int cur = i % 2, pre = 1 - cur;
for (int pres = 0; pres < n; pres++) {
if ((pres & (pres << 1)) != 0) continue;
for (int s = 0; s < n; s++) {
if ((s & (s << 1)) != 0 || (s & pres) != 0) continue;
dp[cur][s] = Math.max(dp[cur][s], dp[pre][pres] + sum(s, houses[i]));
if (i == h - 1) ans = Math.max(ans, dp[cur][s]);
}
}
}
return ans;
}
int sum(int state, int[] row) {
int sum = 0, idx = row.length - 1;
for (;state > 0; state >>= 1, idx--) {
if ((state & 1) > 0) sum += row[idx];
}
return sum;
}
上述我们用了状压DP去解决了这个问题。
时间复杂度大概是(2 ^ l) ^ 2 * h
是指数的复杂度。
下面我们就来看看如何用网络流来优化。
其实学过竞赛的小伙伴，应该就看出来了这是一个最大独立集的题目。
我们把这个矩阵，依次黑白染色。就变成国际象棋棋盘那样，黑白交错的。那么选了白色的点，就不能选黑色的点，就满足了题意。那么所有格子就被划分成了2个点集。黑色点集和白色点集。
我们从黑色点集向白色点集连上对应的边。
我们要做的是求出一个最大的点集（点权和最大）使得点集里的点没有边。
再逆向思考一下，我们本质上要找到一些点，可以覆盖所有的边，然后使得这个点集的点权和最小。这个也是网络流里面的一个叫最小点覆盖的问题。
有了这个最小值。我们想求之前的问题，只需要把所有点求和减去那个最小值。余下的点都可以选。那么这个值就是最大值了。
我们需要把2类点一类和源点S相连，容量为点权。另一类和汇点T相连，容量为点权。中间的边容量为正无穷。这个最小值在网络流里等价于流网络的最小割。
而且最小割和最大流，我们用dinic算法即可。
dinic算法模板
// 下面这组变量是DINIC跑最大流的基础变量。n是点数，m是边数
int N = 20020, M = 300010, inf = (int) 1e9;
// h e ne 3个数组 是数组模拟邻接表的建图方式，加边函数参加ADD
// w 代表 残留网络的剩余容量。 d 是对所有点建立分层图，维护层数
// cur 是当前层优化的数组 S代表源点 T代表汇点
int[] h = new int[N], cur = new int[N], d = new int[N];
int[] e = new int[M], ne = new int[M], w = new int[M];
int S, T, idx = 0;
void add(int a, int b, int c) {
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
e[idx] = a; w[idx] = 0; ne[idx] = h[b]; h[b] = idx++;
}
private long dinic() {
long r = 0, flow;
while (bfs()) while ((flow = find(S, inf)) != 0) r += flow;
return r;
}
// dinic find 函数模板，带当前层优化
private int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
int j = e[i];
cur[u] = i;
if (d[j] == d[u] + 1 && w[i] > 0) {
int v = find(j, Math.min(w[i], limit - flow));
if (v == 0) d[j] = -1;
w[i] -= v; w[i ^ 1] += v; flow += v;
}
}
return flow;
}
// dinic bfs 建分层图模板
private boolean bfs() {
Arrays.fill(d, -1);
cur = h.clone();
Queue<Integer> q = new LinkedList<>();
q.offer(S); d[S] = 0;
while (!q.isEmpty()) {
int a = q.poll();
for (int i = h[a]; i != -1; i = ne[i]) {
int b = e[i];
if (d[b] == -1 && w[i] > 0) {
d[b] = d[a] + 1;
if (b == T) return true;
q.offer(b);
}
}
}
return false;
}
有了网络流的算法工具，下面我们只需要根据不同题目去建对应的图即可。
public int solve2(int[][] houses) {
int hh = houses.length, ll = houses[0].length;
Arrays.fill(h, -1);
S = N - 2; T = N - 1;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int tot = 0;
for (int i = 0; i < hh; i++) {
for (int j = 0; j < ll; j++) {
if ((i + j) % 2 == 1) {
add(S, i * ll + j, houses[i][j]);
for (int[] d : dirs) {
int ny = i + d[0], nx = j + d[1];
if (ny < 0 || nx < 0 || ny == hh || nx == ll) continue;
add(i * ll + j, ny * ll + nx, inf);
}
} else {
add(i * ll + j, T, houses[i][j]);
}
tot += houses[i][j];
}
}
return (int) (tot - dinic());
}
1349. Maximum Students Taking Exam
有了上面的理解，我们可以来看一道LC的真题。是1349题。
我们可以发现和我们之前介绍的HOUSE ROBBER非常像。只是选了一个位置，不是上下左右不能选。而是另外4个格子。同时有一些废弃的座位。
我们同样可以根据一层一层来枚举所有可以放学生的状态，用状压DP去解决这个问题。
public int maxStudents(char[][] ss) {
int h = ss.length, l = ss[0].length;
int[] dp = new int[1 << l];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 0; i < h; i++) {
int[] tmp = new int[dp.length];
Arrays.fill(tmp, -1);
int avail = g(ss[i]);
for (int s = 0; s < dp.length; s++) {
if ((avail & s) != s || (s & (s << 1)) != 0) continue;
for (int pres = 0; pres < dp.length; pres++) {
if (dp[pres] == -1 || (pres & (s << 1)) != 0 || (pres & (s >> 1)) != 0)
continue;
tmp[s] = Math.max(tmp[s], dp[pres] + Integer.bitCount(s));
}
}
dp = tmp;
}
int res = 0;
for (int i = 0; i < dp.length; i++) res = Math.max(res, dp[i]);
return res;
}
int g(char[] cs) {
int s = 0;
for (int i = 0; i < cs.length; i++) {
if (cs[i] == '#') continue;
s |= 1 << i;
}
return s;
}
下面我们可以基于同样的思想用最大独立集去做。
首先我们思考如何划分2类点，通过观察我们可以发现，这次点的划分是按列来的。
列为奇数时是白色点，列为偶数时是黑色点。
其次当一个格子被选择了。他周围6个格子是不能放东西了。如果放了就违反了题目约束。
其次我们还有把已经坏掉的格子给跳过。
所以基于上述3个改动，我们可以在不动DINIC模板下，只要稍微改下建图，就可以用网络流AC掉这个题目。
public int maxStudents(char[][] ss) {
int hh = ss.length, ll = ss[0].length;
Arrays.fill(h, -1);
S = N - 2; T = N - 1;
int[][] dirs = {{0,1},{0,-1},{-1,-1},{-1,1},{1,1},{1,-1}};
int tot = 0;
for (int i = 0; i < hh; i++) {
for (int j = 0; j < ll; j++) {
if (ss[i][j] == '#') continue;
if (j % 2 == 0) {
add(S, i * ll + j, 1);
for (int[] d : dirs) {
int ny = i + d[0], nx = j + d[1];
if (ny < 0 || nx < 0 || ny == hh || nx == ll) continue;
add(i * ll + j, ny * ll + nx, inf);
}
} else {
add(i * ll + j, T, 1);
}
tot += 1;
}
}
return (int) (tot - dinic());
}
最小费用最大流。
下面是一类费用流的问题。费用流问题，我们需要2个算法，一个是EK算法，一个是SPFA算法。SPFA就是经过优化的bellman ford算法。不了解的小伙伴可以去搜索一下。
我们用SPFA 跑出来的就是一条费用最小的增广路。然后我们用EK算法，不断的去做增广。这样可以保证当达到最大流的时候，总费用是最小的。
下面我们给出费用流的模板
// N 代表图的点数，M代表边数
int N = 5050, M = 100100, inf = (int) 1e8;
// e[idx] 记录idx这条边指向哪个点的编号。 ne[idx] 存的是 邻接矩阵下一条边； w存容量； c 存费用
int[] e = new int[M], ne = new int[M], w = new int[M], c = new int[M];
// 每个点的邻接矩阵的第一条边存h, pre[i] 存的是增广路中 i这个点 是哪个边过来的；
// d 存的是这条路里的最小费用， incw 存的是就是这条增广路的增量的流量
int[] h = new int[N], pre = new int[N], d = new int[N], incw = new int[N];
// st 数组表示 spfa 里该元素是否进STACK了
boolean[] st = new boolean[N];
// 源点，汇点，当前最大的边IDX
int S, T, idx = 0;
boolean spfa() {
Arrays.fill(incw, 0);
Arrays.fill(d, inf);
Queue<Integer> q = new LinkedList<>();
d[S] = 0; incw[S] = inf; q.offer(S);
while (!q.isEmpty()) {
int from = q.poll();
st[from] = false;
for (int i = h[from]; i != -1; i = ne[i]) {
int to = e[i];
if (w[i] > 0 && d[to] > d[from] + c[i]) {
d[to] = d[from] + c[i];
pre[to] = i;
incw[to] = Math.min(incw[from], w[i]);
if (!st[to]) {
st[to] = true;
q.offer(to);
}
}
}
}
return incw[T] > 0;
}
int ek() {
int cost = 0;
while (spfa()) {
int t = incw[T];
cost += d[T] * t;
for (int i = T; i != S; i = e[pre[i] ^ 1]) {
w[pre[i]] -= t;
w[pre[i] ^ 1] += t;
}
}
return cost;
}
void add(int a, int b, int cap, int cost) {
e[idx] = b; w[idx] = cap; c[idx] = cost; ne[idx] = h[a]; h[a] = idx++;
e[idx] = a; w[idx] = 0; c[idx] = -cost; ne[idx] = h[b]; h[b] = idx++;
}
上面的模板是求最小费用最大流。
如果题目需要求最大费用最大流。我们可以在设置边的费用的时候，全部取相反数。最后跑最小费用最大流，再取一次相反数。就是最大费用最大流的结果。
1066. Campus Bikes II
这道题就是在一个2D 平面上，散了一些人，和一些自行车。现在要给每个人分配一辆自行车。使得人和车的总距离最小。
这道题因为每个人必须得配一辆车。那么我们就从前往后给每个人发车。一个人可以有K种选择（K为自行车数量），但是前面的人选了一辆车，后面的人就不能选这辆了。
所以后面的人我们需要知道前面的人把哪些车给选了。他要在剩余的车里枚举。
所以我们可以把用掉的自行车 用BIT位表示出来，这个状态可以被记忆化搜索。
那么状态压缩记忆化搜索的代码如下：
class Solution {
public int assignBikes(int[][] workers, int[][] bikes) {
int wl = workers.length, bl = bikes.length;
int[] dp = new int[1 << bl];
return help(0, 0, dp, workers, bikes);
}
private int help(int widx, int used, int[] dp, int[][] workers, int[][] bikes) {
if (widx == workers.length) return 0;
if (dp[used] != 0) return dp[used];
int[] w = workers[widx];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < bikes.length; i++) {
if ((used & (1 << i)) != 0) continue;
ans = Math.min(ans, help(widx + 1, used | (1<<i), dp, workers, bikes) + dis(w, bikes[i]));
}
return dp[used] = ans;
}
private int dis(int[] w, int[] b) {
return Math.abs(w[0] - b[0]) + Math.abs(w[1] - b[1]);
}
}
费用流解法
我们不难发现，如果我们把所有人当做一个集合，所有车当做一个集合。这个图就是一个2分图。源点向所有人连边，所有车向汇点连边。中间的车和人之间，容量都为1，因为1个人只能选1辆车，而费用就是人和车之间的距离。
根据这样来建图。我们跑最大流，就可以确保所有人都会有车。然后基于最大流我们求出最小费用即为答案。
下面我只写了建图函数，其余都是模板部分。
public int assignBikes(int[][] workers, int[][] bikes) {
int wl = workers.length, bl = bikes.length;
Arrays.fill(h, -1);
S = N - 2; T = N - 1;
for (int i = 0; i < wl; i++) add(S, i, 1, 0);
for (int i = 0; i < bl; i++) add(wl + i, T, 1, 0);
for (int i = 0; i < wl; i++) {
for (int j = 0; j < bl; j++) {
add(i, wl + j, 1, dis(workers, bikes, i, j));
}
}
return ek();
}
1595. Minimum Cost to Connect Two Groups of Points
下面是一道新题。这道题就是有2个点集。从一个点集的点到另一个点集的点相连有个COST。题目要求，所有点都至少有一个和另一个点集的点连着的边。要求总COST最小。
按照状压的思路。我们就从前往后枚举第一个点集。和上一道自行车不太一样的是，另一个点集的点可以被重复用。
所以如果第一个点集都连上边了。可能会存在第二个点集还有点没连上边的时候，这个时候用贪心，把第二个点集没连上边的点给连起来。那么就是答案。
并且上一道题，因为状态里1的个数就可以表示遍历到第几个人。这个问题里因为可以重复使用同一个1，所以我们还需要一个维度去记录遍历到第一个点集的第几个点的信息。
class Solution {
int[][] ma;
int[] min2;
int inf = (int) 1e8;
int[][] dp;
int h, l;
public int connectTwoGroups(List<List<Integer>> cost) {
h = cost.size(); l = cost.get(0).size();
ma = new int[h][l];
min2 = new int[l];
Arrays.fill(min2, inf);
for (int i = 0; i < h; i++) {
for (int j = 0; j < l; j++) {
ma[i][j] = cost.get(i).get(j);
min2[j] = Math.min(min2[j], ma[i][j]);
}
}
dp = new int[h + 1][1 << l];
for (int[] i : dp) Arrays.fill(i, -1);
return dfs(0, 0);
}
int dfs(int idx, int st) {
if (dp[idx][st] != -1) return dp[idx][st];
int res = idx == h ? 0 : inf;
if (idx >= h) {
for (int i = 0; i < l; i++) {
if ((st & (1 << i)) == 0) res += min2[i];
}
return dp[idx][st] = res;
} else {
for (int i = 0; i < l; i++) {
res = Math.min(res, ma[idx][i] + dfs(idx + 1, st | (1 << i)));
}
}
return dp[idx][st] = res;
}
}
费用流解法
这道题从费用流的角度，我们要思考的就是，我们需要选出一组边，可以覆盖到所有的点，并且边权和最小。
这类问题又称最小边权覆盖。当边权都为正的时候，我们可以把问题转换为二分图最大代权匹配。那么就和自行车那道问题是一样的了。
首先我们要维护2个数组min1 和 min2。 min1[x]分别表示从集合1里的X点连出去的所有边里的最小边权。MIN2也是同理。
有了这2个数组，我们可以先把SUM(MIN1) 和 SUM(MIN2) 给加起来。 这个是这个问题的上界。也就是最差情况 就是这个解了。 当然有些点，我们可以通过一条边，就连起来2个点。这个时候就可以更优。
所以一旦我们选了这样的边，我们会用这条边的边权 w(i, j) - min1[i] - min2[j], 是为了把开始加进去的2个值减掉，然后替换为这条边的边权。
我们把最优解里用到的这种边的集合称为E。所以答案是 SUM(MIN1) + SUM(MIN2) + SUM(E)
为了让最后的解最小。 前面2个SUM都是定值。所以我们希望sum(E) 最小。
所以我们对这种情况建图，随后跑最小费用最大流。因为这组边的集合可以不是满流，为了运用这个算法，我们需要给每个点 都引入1个容量为1， 费用为0的边。如果走了这条边形成的最大流，就代表这个边不在E这个集合里。
综上。我给出建图方法，其余就是模板了。
int[][] ma;
int[] min1, min2;
public int connectTwoGroups(List<List<Integer>> cost) {
int hh = cost.size(), ll = cost.get(0).size();
ma = new int[hh][ll];
min1 = new int[hh]; min2 = new int[ll];
Arrays.fill(min1, inf); Arrays.fill(min2, inf);
S = N - 2; T = N - 1;
Arrays.fill(h, -1);
for (int i = 0; i < hh; i++) {
for (int j = 0; j < ll; j++) {
ma[i][j] = cost.get(i).get(j);
min2[j] = Math.min(min2[j], ma[i][j]);
min1[i] = Math.min(min1[i], ma[i][j]);
}
}
int tot = 0;
for (int i : min1) tot += i;
for (int i : min2) tot += i;
for (int i = 0; i < hh; i++) {
add(S, i, 1, 0);
for (int j = 0; j < ll; j++) {
if (i == 0) add(hh + j, T, 1, 0);
add(i, hh + j, 1, ma[i][j] - min1[i] - min2[j]);
add(i, hh + j, 1, 0);
}
}
return tot + ek();
}
总结
今天我们介绍了4个LC的题目。分别先从状态压缩的DP入手怎么解决这类问题。然后再切入网络流的解法。其中最大独立集的问题，对应于棋盘类型的2分图的状态压缩。而状压记忆化搜索带权值的问题，我们可以试着想想是不是可以通过费用流来解决。
不过想在比赛中，直接用上费用流的解法，和正确的建图。还是没有捷径的，只能靠平时多做多积累。见多识广才是正道。
网友评论