最小割补充文档及相关习题
2022 年 7 月 19 日晚上 21:30 在解题十分钟直播间讲解最小割解题方法和系列例题。
直播录像在这里
注意 : 这是相关题目的链接补充及代码参考,所有涉及到思路的地方都比较粗糙,看不懂很正常。
Asteroids
3041 – Asteroids
其实这题就是 n × m n \times m n×m 棋盘问题。可以用来练习 dinic。
假设 ( x , y ) (x,y) (x,y) 需要去掉,显然同时划分到不选他们的方案是不合法的,连边 + ∞ +\infty +∞ ,其余根据自己的建模,参考 up 的建模方式即可。
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long longconst int N = 1E3 + 10, M = 2E5 + 10;struct edge{int v, c, ne;edge() {}edge(int v, int c, int ne) : v(v), c(c), ne(ne) {}
}e[M];int n, m, S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = edge(b, c, h[a]);h[a] = idx;
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}int x, y;void solve(){cin >> n >> m;while(m --){cin >> x >> y;add(x, y + n, 1e18);add(y + n, x, 0);}S = 0, T = 2 * n + 1;for(int i = 1; i <= n; i ++){add(S, i, 1);add(i, S, 0);add(i + n, T, 1);add(T, i + n, 0);}cout << dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}
P3231 [HNOI2013] 消毒
[HNOI2013] 消毒 - 洛谷
这是我不独立完成的一道洛谷紫题,实际就是上一题的升级版,二维转三维。
当然这题之所以可做,是因为 a × b × c ≤ 5000 a\times b \times c \leq 5000 a×b×c≤5000 ,也就代表着总有一维 $\leq \sqrt[3] {5000} $ , 大概是 17 数量级。
对于最小的这一维,我们暴搜怎么消毒。
关于消毒,取 min ( x , y , z ) = 1 \min (x,y,z)=1 min(x,y,z)=1 一定是最优的,相当于每次选一个截面消毒,花费一个代价。
暴搜最小的截面之后,剩下的点,已经消毒的直接忽略,没消毒的点,相当于第一个问题了。
注意到,求这个二分图的最小割,也就是求二分图的最大流,同时也就是最大匹配。
所以为了好写代码,匈牙利跑一遍即可。
时间复杂度不会算了已经,大概是 O ( T × 2 17 × b c ) O(T\times 2^{17} \times bc) O(T×217×bc) , 因为匈牙利实际更快,所以这个复杂度应该达不到。
#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 1E4 + 10, M = 2E4 + 10;int a, b, c;
int q[4][N];
int ans, cnt = 0;int h[N], e[M], ne[M], idx = 0;void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int ok[20];
int st[N], match[N];bool find(int u){for(int i = h[u]; ~i; i = ne[i]){int v = e[i];if(!st[v]){st[v] = true;if(!match[v] || find(match[v])){match[v] = u;return true;}}}return false;
}int cal(){int res = 0;memset(h, -1, sizeof h);idx = 0;for(int i = 1; i <= cnt; i ++){if(ok[q[1][i]] == false) {add(q[2][i], q[3][i] + b);add(q[3][i] + b, q[2][i]);}}for(int j = b + 1; j <= b + c; j ++) match[j] = 0;for(int i = 1; i <= b; i ++){for(int j = b + 1; j <= b + c; j ++) st[j] = false;if(find(i)) res ++;}return res;
}void dfs(int u, int v){if(u == a + 1){ans = min(ans, cal() + v);return ;}dfs(u + 1, v);ok[u] = 1;dfs(u + 1, v + 1);ok[u] = 0;
}void solve(){cin >> a >> b >> c;cnt = 0;for(int i = 1; i <= a; i ++){for(int j = 1; j <= b; j ++){for(int k = 1; k <= c; k ++){int x;cin >> x;if(x){q[1][++ cnt] = i, q[2][cnt] = j, q[3][cnt] = k;}}}}ans = 5000;memset(ok, 0, sizeof ok);dfs(1, 0); // 正在考虑第 i 层, 已经花费代价 jcout << ans << '\n';
}signed main(){// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}
P2762 太空飞行计划问题
太空飞行计划问题 - 洛谷
就是课上所讲的设备采购问题,不得不感叹 up 主讲得很好。
其实这是一个算法,或者说是图论的一个知识点吧,叫最大权闭合子图。
闭合子图的定义是,对于有向图 G = ( V , E ) G=(V,E) G=(V,E) ,如果存在子集 S ⊆ V S \subseteq V S⊆V , 满足闭合条件 : 对于任意两个节点 u , v ∈ V u,v\in V u,v∈V , 如果 u ∈ S u \in S u∈S 且存在边 u → v u \rightarrow v u→v ,那么 v v v 也必须属于 S S S 。
我们给每个点一个权值,权值最大的闭合子图就是最大权闭合子图。
我们直接看这道题就可以,会了这道题,你就会发现,其实最大权闭合子图是一个很无聊的东西。
注意,按照 up 的划分方式,我们 dinic 过程中 bfs 找增广路的时候,显然最后最小割断流,因此所有 d ≠ 0 d\neq 0 d=0 的就是 S S S 集合的元素,其余都是 T T T 集合的元素。
#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 210, M = 1E4 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx;
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}int m, n, res = 0;int atS[N], st[N];void dfs(int u){st[u] = atS[u] = 1;for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(!st[v] && e[i].c){dfs(v);}}
}// tips : initialize S, T ; for (u, v, w), add(u, v, w), add(v, u, 0)void solve(){scanf("%lld %lld", &m, &n);S = 0, T = n + m + 1;for(int i = 1; i <= m; i ++){int x, I;scanf("%lld", &x);res += x;add(n + i, T, x);add(T, n + i, 0);while(getchar() == ' '){scanf("%lld", &I);add(I, n + i, 1e18);add(n + i, I, 0);}}for(int i = 1; i <= n; i ++){int x;scanf("%lld", &x);add(S, i, x);add(i, S, 0);}int ans = res - dinic();for(int i = 1; i <= m; i ++){if(d[n + i] == 0) printf("%lld ", i);}puts("");for(int i = 1; i <= n; i ++){if(d[i] == 0) printf("%lld ", i);}printf("\n%lld", ans);
}signed main(){// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0); solve();return 0;
}
/*
void solve(){int n;scanf("%lld", &n);vector<vector<int> > vc(n + 1);for(int i = 1; i <= n; i ++){int x;scanf("%lld", &x);vc[i].push_back(x);while(getchar() == ' '){scanf("%lld", &x);vc[i].push_back(x);}}for(int i = 1; i <= n; i ++){cout << "vector: " << i << '\n';for(auto &nx : vc[i]) cout << nx << ' ';cout << '\n';}
}
*/
tips : 这是题目的读入方式,我认为这个比题面中给出的更好写
void solve(){int n;scanf("%lld", &n);vector<vector<int> > vc(n + 1);for(int i = 1; i <= n; i ++){int x;scanf("%lld", &x);vc[i].push_back(x);while(getchar() == ' '){scanf("%lld", &x);vc[i].push_back(x);}}for(int i = 1; i <= n; i ++){cout << "vector: " << i << '\n';for(auto &nx : vc[i]) cout << nx << ' ';cout << '\n';}
}
P2774 方格取数问题
方格取数问题 - 洛谷
有件事情很有意思,出现在网络流专题的网络流题目难度自动下降一个等级。
不难理解,网络流的多数题目难点首先就在于想到这题可以用网络来做,其次就是建模,建模完成之后,题目就已经结束了。
这道题目也是,其实我们把棋盘看成图的话,相邻的点连边,类似国际象棋的黑白格,这些黑白格就是一张二分图。
这道题目,我们先把所有贡献收集过来,然后用最小割分配每个点,总贡献 - 最小割就是我们最多收集到的贡献。
#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 1E4 + 10, M = 2E5 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx;
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}
/*set N, Minitialize S, T ;for (u, v, w), add(u, v, w), add(v, u, 0)
*/ int n, m, w[110][110];int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};int cal(int x, int y){return (x - 1) * m + y;
}void add(int x, int y){for(int i = 0; i < 4; i ++){int nx = x + dx[i], ny = y + dy[i];if(nx >= 1 && nx <= n && ny >= 1 && ny <= m){add(cal(x, y), cal(nx, ny), 1e18);add(cal(nx, ny), cal(x, y), 0);}}
}void solve(){int ans = 0; cin >> n >> m;S = 0, T = n * m + 1;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){cin >> w[i][j];ans += w[i][j];}}for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){if((i + j) & 1){add(i, j);add(S, cal(i, j), w[i][j]);add(cal(i, j), S, 0);}else{add(cal(i, j), T, w[i][j]);add(T, cal(i, j), 0);}}}cout << ans - dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}
G - Grid Card Game
G - Grid Card Game
对于每个行列,都是二元选择问题,要么选,要么不选。
我们用 S 集合表示选择行但不选择列 ;用 T 集合表示选择列但不选择行。
首先先拿走全部正数代价。然后对于负数格,显然不能同时选择,于是我们队 r → c r\rightarrow c r→c 连一条 + ∞ +\infty +∞ 的边 ;对于正数格,都不选择,会放弃这个价值,从 c → r c\rightarrow r c→r 连一条 x x x 的边 ;对于每个行或者列,如果选择,会扣掉所有负数代价。
用提前拿走的所有价值减掉这个图的 S-T 最小割即可。
#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 210, M = 2E5 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx;
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}
/*set N, Minitialize S, T ;for (u, v, w), add(u, v, w), add(v, u, 0)
*/ int n, m;int a[110][110];void solve(){int res = 0;cin >> n >> m;S = 0, T = n + m + 1;for(int i = 1; i <= n; i ++){int s = 0;for(int j = 1; j <= m; j ++){cin >> a[i][j];if(a[i][j] > 0){add(n + j, i, a[i][j]);add(i, n + j, 0);res += a[i][j];}if(a[i][j] < 0){add(i, n + j, 1e18);add(n + j, i, 0);s += -a[i][j];}}add(i, T, s);add(T, i, 0);}for(int j = 1; j <= m; j ++){int s = 0;for(int i = 1; i <= n; i ++){if(a[i][j] < 0) s += -a[i][j];}add(S, n + j, s);add(n + j, S, 0);}cout << res - dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}
E. Best Subsequence
一切源于此题 。。。。
题目的 set bits 指的数字二进制表示 1 的出现次数。
其实这道题还是不容易想到最小割来解决的。
如果能想到,首先想到,对于每个元素,当然是选择或者不选择,一般会往 DP 去想。
假设 DP 没想到做法吧,你会在思考过程中发现,对于每个数,选择他,那么他的所有二进制 1 都要选。注意题目是 bitwise OR , 我一开始看成 bitwise xor 了,正好 1 | 2 == 1 ^ 2,没太注意。
既然是按位或,对于每个数,看做点,每个位 1 ,看做点。
最多 n + 60 + 2 n+60+2 n+60+2 个点,多出来的是 S = 0 , T = n + 60 + 1 S=0,T=n+60+1 S=0,T=n+60+1 。
S 集合表示选数字,选二进制,T 集合相反。
不能选数字不选二进制,每个数字往他的 bit sets 连 1.
先拿走 n 个贡献,不选数字,割掉贡献,S 向 i 连 1 ;
选择位,割掉贡献,位向 T 连 1.
n - 最小割就是答案。
#include<bits/stdc++.h>
using namespace std;
#define int long longconstexpr int N = 210, M = 2E5 + 10;struct edge{int v, c, ne;
}e[M];int S, T;
int h[N], idx = 1; // idx = 1 方便找反向边
int d[N], cur[N];void add(int a, int b, int c) {e[++ idx] = {b, c, h[a]}; h[a] = idx;
}bool bfs(){ // 对点分层memset(d, 0, sizeof d);queue<int> q;q.push(S);d[S] = 1;while(q.size()){int u = q.front();q.pop();for(int i = h[u]; i; i = e[i].ne){int v = e[i].v;if(d[v] == 0 && e[i].c){d[v] = d[u] + 1;q.push(v);if(v == T) return true;}}}return false;
}int dfs(int u, int rf){ // 从 u 点出发, 有 rf 流量, 留到终点最大流if(u == T) return rf;int sum = 0; // 最大流for(int i = cur[u]; i; i = e[i].ne){cur[u] = i; // 当前弧优化int v = e[i].v;if(d[v] == d[u] + 1 && e[i].c){int f = dfs(v, min(e[i].c, rf));e[i].c -= f;e[i ^ 1].c += f;sum += f;rf -= f;if(!rf) break; // 剩余流量优化}}if(sum == 0) d[u] = 0; // 残枝优化return sum;
}int dinic(){int flow = 0;while(bfs()){memcpy(cur, h, sizeof h);flow += dfs(S, 1e18);}return flow;
}
/*set N, Minitialize S, T ;for (u, v, w), add(u, v, w), add(v, u, 0)
*/ int n, a[110];void solve(){memset(h, 0, sizeof h);idx = 1;cin >> n;S = 0, T = n + 60 + 1;for(int i = 1; i <= n; i ++){cin >> a[i];add(S, i, 1);add(i, S, 0);for(int j = 0; j < 60; j ++){if(a[i] >> j & 1){add(i, n + j + 1, 1e18);add(n + j + 1, i, 0);}}}for(int j = 1; j <= 60; j ++){add(n + j, T, 1);add(T, n + j, 0);}cout << n - dinic() << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}
以下是原文档,需要的可以去 up 主的github 仓库下载
网络流与最小割
2022 年 7 月 19 日晚上 21:30 在解题十分钟直播间讲解最小割解题方法和系列例题。
直播录像在这里
网络流的定义:
- 有一个 s 点有一个 t 点,以及若干其它点
- 有若干有向边。其中 s 点没有入边,t 点没有出边
- 对于除了 s 点和 t 点以外的所有点,入流量之和等于出流量之和
- 形象的比喻想象水管,s 点是无限的水源,t 点是无限的出口,边的权值等于管的容量
- 整个网络同时能通过的最大流量,这个流量等于 s 点的所有出流量,等于 t 点的所有入流量
割的定义:
- 设置两个集合 S 集合和 T 集合,且 s 点属于 S 集合,t 点属于 T 集合
- 其它所有点属于 S 集合或 T 集合之一
- 所有来自于 S 集合,指向 T 集合的边,权值之和为割的大小
定理:
- 最小割 = 最大流
- 直观理解就是 最小割的边满流的情况下,无法再找到增加流量的办法
能否套用最小割方法的判断:
- 把最少/最小代价对应到最小割
- 把二元选择问题 改变为集合选择问题
- 不合法的方案,定义成流量无穷大的边
建图过程:
- 根据可以做二元选择的对象定义所有的点
- 根据不合法方案连接无穷大的边,明确点的集合归属含义
- 根据点的集合归属含义,明确所有需要支付的成本
额外思路:
- 先假设能获得所有收益,然后把得不到的收益也记作成本,来解决最大化收益问题
棋子问题
有 N*M 的棋盘,上面有 K 个棋子,位于 Ai 行 Bi 列。
一次操作可以消除一行的棋子或者消除一列的棋子。
问最少要多少次操作,才能消灭所有的棋子?
1 ≤ N,M ≤ 100
思考过程:
- 最少次操作 => 最小代价 => 最小割(把边看做代价)
- 每一行,可以选择消除或不消除
- 每一列,可以选择消除或不消除
- 所以网络中的点是 行 与 列
- 不合法的方案,表示有棋子没有被消除。
建模过程:
- 行属于 S 集合表示不消除,属于 T 集合表示消除
- 列属于 T 集合表示不消除,属于 S 集合表示消除
- 不合法方案的边:
- 对于为 1 的单元格,行不消除且列不消除非法
- 对应单元格建立行指向列的无穷大流量边
- 支付成本:
- s 到行,流量为 1
- 列到 t,流量为 1
设备采购问题
有 N 种设备,采购价格分别是 A1,A1,…AN
和 M 个项目,项目收益分别是 B1,B1,…BM
另外有 K 个约束条件,Ci,Di 表示完成 Di 号项目,必须要拥有 Ci 号设备。
问最高能获得的利润是多少(利润等于收益-成本)
思考过程:
- 先假设能获得所有收益,然后把得不到的收益也记作成本
- 设备:采购与不采购;项目:做与不做
- 不合法方案:项目依赖的设备没有采购,但又要做对应项目
建图过程:
- 设备属于 S 集合表示不采购,属于 T 集合表示采购
- 项目属于 S 集合表示不做,属于 T 集合表示做
- 不合法方案:
- 项目依赖设备,但设备未采购,不合法
- 有依赖时,从设备指向项目,流量无穷大
- 支付成本:
- 设备采购支付成本,s 点指向设备,流量为采购成本
- 项目不做支付损失,项目指向 t 点,流量为项目收益
取数问题
在一个 M*N 的棋盘中,每个方格有一个正整数。现在要从方格中取若干个数,使任意 2 个数所在方格没有公共边,并使取出的数总和最大。试设计一个满足要求的取数算法。
思考过程:
- 先假设能获得所有数,然后建图使方案合法
- 每个数选择与不选择
- 不合法的方案:相邻的格子不能同时选
建图过程:
- 经过尝试和思考,得出结论,区分坐标奇偶性(横坐标和纵坐标之和的奇偶性)
- 偶数格属于 S 集合表示选择,属于 T 集合表示不选择
- 奇数格属于 T 集合表示选择,属于 S 集合表示不选择
- 不合法方案:
- 相邻的格子不能同时选
- 相邻的格子,从偶数格向奇数格建边,流量无穷大
- 支付代价
- 偶数格不选择,s 向偶数格建边,流量为格子的值
- 奇数格不选择,奇数格向 t 建边,流量为格子的值
另一个棋子问题
本题来自于AtCode ABC259
有 N*M 的棋盘,每个方格有一个数,其中有正数也有负数。要求选定其中的若干行和若干列,满足:
- 要求负数的格子不能同时选择所在行和所在列。
如果方格所在的行或所在的列被选中,它的分数被加到总分上,不论是正数还是负数。如果行和列同时被选中,分数也只累加一次。
试设计一个算法,问能得到的最大得分是多少。
思考过程:
- 记所有正数之和为最大收益,考虑需要支付的成本
- 行:选择与不选择,列:选择与不选择
- 不合法方案:负数格的行与列不能同时选择
建图过程:
- 行选择:属于 S 集合;不选择:属于 T 集合
- 列选择:属于 T 集合;不选择:属于 S 集合
- 不合法方案:
- 负数格不能同时选择所在行和所在列
- 负数格从行向列建立流量无穷大的边
- 支付成本:
- 行选择,支付该行所有负数格成本,行到 t 连边,权值为该行所有负数的绝对值和
- 列选择,支付该列所有负数格成本,s 到列连边,权值为该列所有负数的绝对值和
- 正数格,行和列都不选择,支付放弃的成本,列到行建边,权值为该格的值