今天這期對(duì)LC比賽來(lái)說(shuō)有點(diǎn)超綱。因?yàn)橐话鉒C出這類(lèi)題的話(huà)，你能夠用狀壓DP或者其他手段去解決的。而網(wǎng)絡(luò)流是能夠處理更大規(guī)模這類(lèi)問(wèn)題的算法。所以今天我們就來(lái)看一下，這類(lèi)問(wèn)題是怎么從狀壓DP入手解決，又是怎么從網(wǎng)絡(luò)流來(lái)提升效率的。
House Robber
小伙伴L(zhǎng)C刷的多的話(huà)，一定知道這個(gè)小偷偷房子的系列。在LC的題目中，房子是排成一條線，一棵樹(shù)，或者一個(gè)環(huán)。那么要求是拿了一幢房子的財(cái)寶，它相鄰2個(gè)房子的財(cái)寶就不能拿。問(wèn)如何獲得最大價(jià)值。
在線性的結(jié)構(gòu)下，我們用一維DP即可解決這個(gè)問(wèn)題。
dp[i] 代表到數(shù)組前I個(gè)的時(shí)候，最大的價(jià)值是多少。那么轉(zhuǎn)移無(wú)非2種，一種是我取了最后一個(gè)房子的物品。那么dp[i] = dp[i - 2] + val[i]
或者我不取，那么dp[i] = dp[i - 1];
如果拓展到環(huán)上，我們只需要拆成2個(gè)子問(wèn)題，從[0, n-1] 和 [1, n] 2個(gè)段去考慮
如果拓展到樹(shù)上，就是維護(hù)2個(gè)變量，一個(gè)是拿當(dāng)前節(jié)點(diǎn)可以有的最大值，一個(gè)是不拿可以有的最大值。那么處理完2個(gè)孩子之后，對(duì)自己的節(jié)點(diǎn)，就可以根據(jù)2個(gè)孩子的這2個(gè)信息。維護(hù)出自己的這2個(gè)信息，RETURN 到上層。
這3種類(lèi)型的題目，小伙伴們可以自行去LC上學(xué)習(xí)，還是比較簡(jiǎn)單的。
擴(kuò)展到2維
下面這個(gè)問(wèn)題，我們把線性的房子，擴(kuò)展到平面。我們給定一個(gè)矩陣，矩陣?yán)锏闹稻褪欠孔拥呢?cái)寶數(shù)量。小偷拿了一個(gè)房子之后，它上下左右的房子是不能偷的。這個(gè)應(yīng)該怎么做呢？
這個(gè)問(wèn)題就需要用到狀壓DP了，因?yàn)榍耙粚拥哪梅〞?huì)影響到下一層的拿法。所以我們必須把前一層的所有拿法都算好。然后去算下一層的時(shí)候，就可以用O(1)的時(shí)間得到前一層對(duì)應(yīng)的值。
dp[i][st] 就是代表我拿到第I層，第I層是ST的拿法，的最大價(jià)值是多少。
這個(gè)ST 其實(shí)是位壓縮的值。比如1010 就代表拿了矩陣第i行的0號(hào)元素和2號(hào)元素。
所以這就要求這個(gè)矩陣的最大寬度是32.因?yàn)镮NT只有32位。如果真到了32位，這個(gè)時(shí)間復(fù)雜度也是會(huì)爆掉的。所以這類(lèi)問(wèn)題一般在1秒內(nèi)大約可以解決長(zhǎng)度在10-13的問(wèn)題。
首先我們預(yù)處理第0行的，所有狀態(tài)；注意有些是非法狀態(tài)，比如相鄰2個(gè)1. 0110 這種結(jié)構(gòu)是會(huì)觸發(fā)報(bào)警的，所以要避免。
避免也很簡(jiǎn)單(state & (state << 1)) != 0判斷一下即可。
然后下面是3層循環(huán)，第一層是遍歷層數(shù)，然后看前一層的狀態(tài)，和這一層的狀態(tài)。我們要過(guò)濾掉左右相鄰的就是用上述方法。
隨后上下相鄰的過(guò)濾法也很簡(jiǎn)單
(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去解決了這個(gè)問(wèn)題。
時(shí)間復(fù)雜度大概是(2 ^ l) ^ 2 * h
是指數(shù)的復(fù)雜度。
下面我們就來(lái)看看如何用網(wǎng)絡(luò)流來(lái)優(yōu)化。
其實(shí)學(xué)過(guò)競(jìng)賽的小伙伴，應(yīng)該就看出來(lái)了這是一個(gè)最大獨(dú)立集的題目。
我們把這個(gè)矩陣，依次黑白染色。就變成國(guó)際象棋棋盤(pán)那樣，黑白交錯(cuò)的。那么選了白色的點(diǎn)，就不能選黑色的點(diǎn)，就滿(mǎn)足了題意。那么所有格子就被劃分成了2個(gè)點(diǎn)集。黑色點(diǎn)集和白色點(diǎn)集。
我們從黑色點(diǎn)集向白色點(diǎn)集連上對(duì)應(yīng)的邊。
我們要做的是求出一個(gè)最大的點(diǎn)集（點(diǎn)權(quán)和最大）使得點(diǎn)集里的點(diǎn)沒(méi)有邊。
再逆向思考一下，我們本質(zhì)上要找到一些點(diǎn)，可以覆蓋所有的邊，然后使得這個(gè)點(diǎn)集的點(diǎn)權(quán)和最小。這個(gè)也是網(wǎng)絡(luò)流里面的一個(gè)叫最小點(diǎn)覆蓋的問(wèn)題。
有了這個(gè)最小值。我們想求之前的問(wèn)題，只需要把所有點(diǎn)求和減去那個(gè)最小值。余下的點(diǎn)都可以選。那么這個(gè)值就是最大值了。
我們需要把2類(lèi)點(diǎn)一類(lèi)和源點(diǎn)S相連，容量為點(diǎn)權(quán)。另一類(lèi)和匯點(diǎn)T相連，容量為點(diǎn)權(quán)。中間的邊容量為正無(wú)窮。這個(gè)最小值在網(wǎng)絡(luò)流里等價(jià)于流網(wǎng)絡(luò)的最小割。
而且最小割和最大流，我們用dinic算法即可。
dinic算法模板
// 下面這組變量是DINIC跑最大流的基礎(chǔ)變量。n是點(diǎn)數(shù)，m是邊數(shù)
int N = 20020, M = 300010, inf = (int) 1e9;
// h e ne 3個(gè)數(shù)組 是數(shù)組模擬鄰接表的建圖方式，加邊函數(shù)參加ADD
// w 代表 殘留網(wǎng)絡(luò)的剩余容量。 d 是對(duì)所有點(diǎn)建立分層圖，維護(hù)層數(shù)
// cur 是當(dāng)前層優(yōu)化的數(shù)組 S代表源點(diǎn) T代表匯點(diǎn)
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 函數(shù)模板，帶當(dāng)前層優(yōu)化
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;
}
有了網(wǎng)絡(luò)流的算法工具，下面我們只需要根據(jù)不同題目去建對(duì)應(yīng)的圖即可。
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
有了上面的理解，我們可以來(lái)看一道LC的真題。是1349題。
我們可以發(fā)現(xiàn)和我們之前介紹的HOUSE ROBBER非常像。只是選了一個(gè)位置，不是上下左右不能選。而是另外4個(gè)格子。同時(shí)有一些廢棄的座位。
我們同樣可以根據(jù)一層一層來(lái)枚舉所有可以放學(xué)生的狀態(tài)，用狀壓DP去解決這個(gè)問(wèn)題。
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;
}
下面我們可以基于同樣的思想用最大獨(dú)立集去做。
首先我們思考如何劃分2類(lèi)點(diǎn)，通過(guò)觀察我們可以發(fā)現(xiàn)，這次點(diǎn)的劃分是按列來(lái)的。
列為奇數(shù)時(shí)是白色點(diǎn)，列為偶數(shù)時(shí)是黑色點(diǎn)。
其次當(dāng)一個(gè)格子被選擇了。他周?chē)?個(gè)格子是不能放東西了。如果放了就違反了題目約束。
其次我們還有把已經(jīng)壞掉的格子給跳過(guò)。
所以基于上述3個(gè)改動(dòng)，我們可以在不動(dòng)DINIC模板下，只要稍微改下建圖，就可以用網(wǎng)絡(luò)流AC掉這個(gè)題目。
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());
}
最小費(fèi)用最大流。
下面是一類(lèi)費(fèi)用流的問(wèn)題。費(fèi)用流問(wèn)題，我們需要2個(gè)算法，一個(gè)是EK算法，一個(gè)是SPFA算法。SPFA就是經(jīng)過(guò)優(yōu)化的bellman ford算法。不了解的小伙伴可以去搜索一下。
我們用SPFA 跑出來(lái)的就是一條費(fèi)用最小的增廣路。然后我們用EK算法，不斷的去做增廣。這樣可以保證當(dāng)達(dá)到最大流的時(shí)候，總費(fèi)用是最小的。
下面我們給出費(fèi)用流的模板
// N 代表圖的點(diǎn)數(shù)，M代表邊數(shù)
int N = 5050, M = 100100, inf = (int) 1e8;
// e[idx] 記錄idx這條邊指向哪個(gè)點(diǎn)的編號(hào)。 ne[idx] 存的是 鄰接矩陣下一條邊； w存容量； c 存費(fèi)用
int[] e = new int[M], ne = new int[M], w = new int[M], c = new int[M];
// 每個(gè)點(diǎn)的鄰接矩陣的第一條邊存h, pre[i] 存的是增廣路中 i這個(gè)點(diǎn) 是哪個(gè)邊過(guò)來(lái)的；
// d 存的是這條路里的最小費(fèi)用， incw 存的是就是這條增廣路的增量的流量
int[] h = new int[N], pre = new int[N], d = new int[N], incw = new int[N];
// st 數(shù)組表示 spfa 里該元素是否進(jìn)STACK了
boolean[] st = new boolean[N];
// 源點(diǎn)，匯點(diǎn)，當(dāng)前最大的邊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++;
}
上面的模板是求最小費(fèi)用最大流。
如果題目需要求最大費(fèi)用最大流。我們可以在設(shè)置邊的費(fèi)用的時(shí)候，全部取相反數(shù)。最后跑最小費(fèi)用最大流，再取一次相反數(shù)。就是最大費(fèi)用最大流的結(jié)果。
1066. Campus Bikes II
這道題就是在一個(gè)2D 平面上，散了一些人，和一些自行車(chē)?，F(xiàn)在要給每個(gè)人分配一輛自行車(chē)。使得人和車(chē)的總距離最小。
這道題因?yàn)槊總€(gè)人必須得配一輛車(chē)。那么我們就從前往后給每個(gè)人發(fā)車(chē)。一個(gè)人可以有K種選擇（K為自行車(chē)數(shù)量），但是前面的人選了一輛車(chē)，后面的人就不能選這輛了。
所以后面的人我們需要知道前面的人把哪些車(chē)給選了。他要在剩余的車(chē)?yán)锩杜e。
所以我們可以把用掉的自行車(chē) 用BIT位表示出來(lái)，這個(gè)狀態(tài)可以被記憶化搜索。
那么狀態(tài)壓縮記憶化搜索的代碼如下：
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]);
}
}
費(fèi)用流解法
我們不難發(fā)現(xiàn)，如果我們把所有人當(dāng)做一個(gè)集合，所有車(chē)當(dāng)做一個(gè)集合。這個(gè)圖就是一個(gè)2分圖。源點(diǎn)向所有人連邊，所有車(chē)向匯點(diǎn)連邊。中間的車(chē)和人之間，容量都為1，因?yàn)?個(gè)人只能選1輛車(chē)，而費(fèi)用就是人和車(chē)之間的距離。
根據(jù)這樣來(lái)建圖。我們跑最大流，就可以確保所有人都會(huì)有車(chē)。然后基于最大流我們求出最小費(fèi)用即為答案。
下面我只寫(xiě)了建圖函數(shù)，其余都是模板部分。
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個(gè)點(diǎn)集。從一個(gè)點(diǎn)集的點(diǎn)到另一個(gè)點(diǎn)集的點(diǎn)相連有個(gè)COST。題目要求，所有點(diǎn)都至少有一個(gè)和另一個(gè)點(diǎn)集的點(diǎn)連著的邊。要求總COST最小。
按照狀壓的思路。我們就從前往后枚舉第一個(gè)點(diǎn)集。和上一道自行車(chē)不太一樣的是，另一個(gè)點(diǎn)集的點(diǎn)可以被重復(fù)用。
所以如果第一個(gè)點(diǎn)集都連上邊了?？赡軙?huì)存在第二個(gè)點(diǎn)集還有點(diǎn)沒(méi)連上邊的時(shí)候，這個(gè)時(shí)候用貪心，把第二個(gè)點(diǎn)集沒(méi)連上邊的點(diǎn)給連起來(lái)。那么就是答案。
并且上一道題，因?yàn)闋顟B(tài)里1的個(gè)數(shù)就可以表示遍歷到第幾個(gè)人。這個(gè)問(wèn)題里因?yàn)榭梢灾貜?fù)使用同一個(gè)1，所以我們還需要一個(gè)維度去記錄遍歷到第一個(gè)點(diǎn)集的第幾個(gè)點(diǎn)的信息。
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;
}
}
費(fèi)用流解法
這道題從費(fèi)用流的角度，我們要思考的就是，我們需要選出一組邊，可以覆蓋到所有的點(diǎn)，并且邊權(quán)和最小。
這類(lèi)問(wèn)題又稱(chēng)最小邊權(quán)覆蓋。當(dāng)邊權(quán)都為正的時(shí)候，我們可以把問(wèn)題轉(zhuǎn)換為二分圖最大代權(quán)匹配。那么就和自行車(chē)那道問(wèn)題是一樣的了。
首先我們要維護(hù)2個(gè)數(shù)組min1 和 min2。 min1[x]分別表示從集合1里的X點(diǎn)連出去的所有邊里的最小邊權(quán)。MIN2也是同理。
有了這2個(gè)數(shù)組，我們可以先把SUM(MIN1) 和 SUM(MIN2) 給加起來(lái)。 這個(gè)是這個(gè)問(wèn)題的上界。也就是最差情況 就是這個(gè)解了。 當(dāng)然有些點(diǎn)，我們可以通過(guò)一條邊，就連起來(lái)2個(gè)點(diǎn)。這個(gè)時(shí)候就可以更優(yōu)。
所以一旦我們選了這樣的邊，我們會(huì)用這條邊的邊權(quán) w(i, j) - min1[i] - min2[j], 是為了把開(kāi)始加進(jìn)去的2個(gè)值減掉，然后替換為這條邊的邊權(quán)。
我們把最優(yōu)解里用到的這種邊的集合稱(chēng)為E。所以答案是 SUM(MIN1) + SUM(MIN2) + SUM(E)
為了讓最后的解最小。 前面2個(gè)SUM都是定值。所以我們希望sum(E) 最小。
所以我們對(duì)這種情況建圖，隨后跑最小費(fèi)用最大流。因?yàn)檫@組邊的集合可以不是滿(mǎn)流，為了運(yùn)用這個(gè)算法，我們需要給每個(gè)點(diǎn) 都引入1個(gè)容量為1， 費(fèi)用為0的邊。如果走了這條邊形成的最大流，就代表這個(gè)邊不在E這個(gè)集合里。
綜上。我給出建圖方法，其余就是模板了。
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();
}
總結(jié)
今天我們介紹了4個(gè)LC的題目。分別先從狀態(tài)壓縮的DP入手怎么解決這類(lèi)問(wèn)題。然后再切入網(wǎng)絡(luò)流的解法。其中最大獨(dú)立集的問(wèn)題，對(duì)應(yīng)于棋盤(pán)類(lèi)型的2分圖的狀態(tài)壓縮。而狀壓記憶化搜索帶權(quán)值的問(wèn)題，我們可以試著想想是不是可以通過(guò)費(fèi)用流來(lái)解決。
不過(guò)想在比賽中，直接用上費(fèi)用流的解法，和正確的建圖。還是沒(méi)有捷徑的，只能靠平時(shí)多做多積累。見(jiàn)多識(shí)廣才是正道。
